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