1. 題目解析與核心思路這道題目來自螞蟻集團2026年暑期實習開發(fā)崗的筆試環(huán)節(jié)考察的是基礎(chǔ)的數(shù)論知識和編程實現(xiàn)能力。題目要求我們處理質(zhì)數(shù)與合數(shù)的相關(guān)問題這在算法面試中屬于中等偏下難度的題目但非常能考察候選人的基礎(chǔ)編碼能力和數(shù)學思維。1.1 題目要求理解題目通常會給出一個具體的數(shù)值范圍或條件要求我們判斷某個數(shù)是否為質(zhì)數(shù)生成某個范圍內(nèi)的所有質(zhì)數(shù)計算質(zhì)數(shù)或合數(shù)的某種統(tǒng)計特征對質(zhì)數(shù)和合數(shù)進行某種組合操作這類問題的核心在于高效實現(xiàn)質(zhì)數(shù)判斷和生成算法同時處理好邊界條件和特殊情況。1.2 質(zhì)數(shù)判斷的優(yōu)化思路最基礎(chǔ)的質(zhì)數(shù)判斷方法是試除法即檢查該數(shù)是否能被2到√n之間的整數(shù)整除。但這種方法的復雜度是O(√n)當需要處理大量數(shù)字時會非常低效。我們可以采用以下優(yōu)化策略預處理法使用埃拉托斯特尼篩法埃氏篩預先計算出范圍內(nèi)的所有質(zhì)數(shù)6n±1法則除了2和3所有質(zhì)數(shù)都可以表示為6n±1的形式米勒-拉賓素性測試對于極大數(shù)的概率性判斷方法提示在筆試環(huán)境下通常使用埃氏篩就能滿足性能要求且實現(xiàn)簡單不易出錯2. Java實現(xiàn)方案2.1 基礎(chǔ)質(zhì)數(shù)判斷public static boolean isPrime(int n) { if (n 1) return false; if (n 2) return true; if (n % 2 0) return false; for (int i 3; i * i n; i 2) { if (n % i 0) { return false; } } return true; }2.2 埃拉托斯特尼篩法實現(xiàn)public static ListInteger sieveOfEratosthenes(int limit) { boolean[] isPrime new boolean[limit 1]; Arrays.fill(isPrime, true); isPrime[0] isPrime[1] false; for (int i 2; i * i limit; i) { if (isPrime[i]) { for (int j i * i; j limit; j i) { isPrime[j] false; } } } ListInteger primes new ArrayList(); for (int i 2; i limit; i) { if (isPrime[i]) { primes.add(i); } } return primes; }2.3 性能優(yōu)化技巧位圖優(yōu)化使用BitSet代替boolean數(shù)組可以減少內(nèi)存使用分段篩法處理極大范圍時可以分段進行篩法處理并行計算對于多核環(huán)境可以將篩法過程并行化3. C實現(xiàn)方案3.1 基礎(chǔ)質(zhì)數(shù)判斷bool isPrime(int n) { if (n 1) return false; if (n 2) return true; if (n % 2 0) return false; for (int i 3; i * i n; i 2) { if (n % i 0) { return false; } } return true; }3.2 埃氏篩實現(xiàn)vectorint sieveOfEratosthenes(int limit) { vectorbool isPrime(limit 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i limit; i) { if (isPrime[i]) { for (int j i * i; j limit; j i) { isPrime[j] false; } } } vectorint primes; for (int i 2; i limit; i) { if (isPrime[i]) { primes.push_back(i); } } return primes; }3.3 C特有優(yōu)化內(nèi)存預分配vector預先reserve足夠空間避免多次擴容編譯器優(yōu)化使用-O2或-O3優(yōu)化級別內(nèi)聯(lián)匯編對關(guān)鍵循環(huán)可以使用內(nèi)聯(lián)匯編進一步優(yōu)化4. Python實現(xiàn)方案4.1 基礎(chǔ)質(zhì)數(shù)判斷def is_prime(n): if n 1: return False if n 2: return True if n % 2 0: return False for i in range(3, int(n**0.5) 1, 2): if n % i 0: return False return True4.2 埃氏篩實現(xiàn)def sieve_of_eratosthenes(limit): is_prime [True] * (limit 1) is_prime[0] is_prime[1] False for i in range(2, int(limit**0.5) 1): if is_prime[i]: for j in range(i*i, limit1, i): is_prime[j] False primes [i for i, prime in enumerate(is_prime) if prime] return primes4.3 Python特有優(yōu)化使用numpy對于大數(shù)據(jù)量使用numpy數(shù)組可以顯著提高性能生成器表達式處理大范圍時使用生成器節(jié)省內(nèi)存緩存結(jié)果使用functools.lru_cache緩存計算結(jié)果5. 常見問題與調(diào)試技巧5.1 邊界條件處理0和1它們既不是質(zhì)數(shù)也不是合數(shù)負數(shù)題目通常要求處理正整數(shù)大數(shù)處理注意數(shù)據(jù)類型的范圍限制5.2 性能問題排查無限循環(huán)確保循環(huán)終止條件正確數(shù)組越界篩法時注意數(shù)組大小類型溢出大數(shù)計算時使用long或BigInteger5.3 測試用例設(shè)計好的測試用例應(yīng)該包含小質(zhì)數(shù)2, 3, 5小合數(shù)4, 6, 8邊界值0, 1, 最大允許值平方數(shù)9, 16, 25大質(zhì)數(shù)如1047296. 面試準備建議掌握基礎(chǔ)算法除了埃氏篩還要了解歐拉篩等更高效的算法復雜度分析能清晰解釋算法的時間和空間復雜度代碼風格注重變量命名、函數(shù)拆分和注釋溝通能力在編碼過程中解釋自己的思路異常處理考慮輸入驗證和錯誤處理在實際面試中這類題目往往只是起點面試官可能會基于你的解決方案進行擴展提問比如如何優(yōu)化內(nèi)存使用如何處理極大范圍的質(zhì)數(shù)生成如何將算法并行化我建議在準備階段不僅要寫出正確的代碼還要思考這些可能的擴展問題準備好相應(yīng)的解決方案。在螞蟻這類頂級互聯(lián)網(wǎng)公司的面試中單純正確但平庸的解決方案往往不夠需要展現(xiàn)出對問題的深入理解和優(yōu)化能力。