從最近素數問題看算法優化：試除法到篩法再到預計算質數表的極致提速

問題描述

給定整數 X，找出與其距離最近的素數。若 X 本身是素數則返回 X；若兩側距離相等，返回較大者。多組查詢，需高效批量處理。

演進歷程與性能對比

最終方案核心代碼解析

1. 預計算質數表 precalc

void precalc(int size, int *primes, int &pnum) {\
    bool *psum = new bool[size+1];\
    memset(psum, true, size+1);  // 默認全為質數\
    for (int j = 4; j <= size; j += 2) psum[j] = false;  // 剔除偶數\
    primes[0] = 2; pnum = 1;\
    for (int i = 3; i*i <= size; ++i) {\
        if (psum[i]) {\
            primes[pnum++] = i;\
            for (int j = i*i; j <= size; j += i<<1) psum[j] = false;  // 步長 2i\
        }\
    }\
    for (int i = 3; i <= size; ++i) if (psum[i]) primes[pnum++] = i;\
    delete [] psum;\
}

• size = √maxX：查詢最大值的平方根，因合數必有 ≤√n 的質因子。
• 位圖 psum 標記合數，primes 存儲質數列表。
• 優化：剔除偶數、從 i² 開始、步長 2i（跳過偶數倍）。

2. 質數判斷 isPrime5

bool isPrime5(int num, const int *primes, int pnum) {\
    for (int i = 0; i < pnum && primes[i]*primes[i] < num; ++i) {\
        if (num % primes[i] == 0) return false;\
    }\
    return true;\
}

• 僅嘗試除以預計算表中的質數，直到質數平方超過 num。
• 極大減少取模次數：對 10⁹ 級數字，僅需試除 ~3400 個質數（π(√10⁹)≈3401），而非 31622 次整數試除。

3. 最近素數搜索 get_nearest

int get_nearest(int num, const int *primes, int pnum) {\
    if (isPrime5(num, primes, pnum)) return num;\
    int len = (num % 2 == 0) ? 1 : 2;  // 偶數從±1開始，奇數從±2開始(保持奇數)\
    while (true) {\
        if (isPrime5(num + len, primes, pnum)) return num + len;\
        if (isPrime5(num - len, primes, pnum)) return num - len;\
        len += 2;\
    }\
}

• 利用「除 2 外質數皆為奇數」特性，步長為 2，交替向外擴展。
• 優先檢查 num+len，滿足「距離相等取大者」要求。

4. 主流程

int maxnum = 0;\
for (i=0; i

核心洞見總結

避免重複計算：多次查詢場景下，預計算共享數據結構是性能提升的銀彈。
數學性質指導優化：質因子 ≤ √n、質數多為奇數、篩法步長優化，均源於數論基本定理。
空間換時間：O(√max) 空間換取 O(π(√n)) 查詢，極高性價比。
工程化細節：new/delete 管理內存、memset 批量初始化、引用傳遞 pnum 返回質數個數，代碼健壯可維護。


擴展應用

大規模質數判斷（密碼學、哈希表質數容量選擇）。
區間質數計數（Meissel-Lehmer 算法基礎）。
競賽編程模板：預計算質數表通用模塊。


從 12 秒到 0.02 秒，578 倍提速，不靠硬件升級，純粹算法與數據結構重設計。這正是「從關於素數的算法題來學習如何提高代碼效率」的最生動註腳。