如何用算法高效尋找素數(shù)？

華府九五二七 2019-11-15

展開全文

預(yù)計閱讀時間：5 分鐘

素數(shù)的定義很簡單，如果一個數(shù)如果只能被 1 和它本身整除，那么這個數(shù)就是素數(shù)。

不要覺得素數(shù)的定義簡單，恐怕沒多少人真的能把素數(shù)相關(guān)的算法寫得高效。本文就主要聊這樣一個函數(shù)：

// 返回區(qū)間 [2, n) 中有幾個素數(shù) 
int countPrimes(int n)

// 比如 countPrimes(10) 返回 4
// 因為 2,3,5,7 是素數(shù)

你會如何寫這個函數(shù)？當(dāng)然可以這樣寫：

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim(i)) count++;
    return count;
}

// 判斷整數(shù) n 是否是素數(shù)
boolean isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            // 有其他整除因子
            return false;
    return true;
}

這樣寫的話時間復(fù)雜度 O(n^2)，問題很大。首先你用 isPrime 函數(shù)來輔助的思路就不夠高效；而且就算你要用 isPrime 函數(shù)，這樣實現(xiàn)也是存在計算冗余的。

先來簡單說下如果你要判斷一個數(shù)是不是素數(shù)，應(yīng)該如何寫算法。只需稍微修改一下上面的 isPrime 代碼中的 for 循環(huán)條件：

boolean isPrime(int n) {
    for (int i = 2; i * i <= n; i++)
        ...
}

換句話說，i不需要遍歷到n，而只需要到sqrt(n)即可。為什么呢，我們舉個例子，假設(shè)n = 12。

12 = 2 × 6
12 = 3 × 4
12 = sqrt(12) × sqrt(12)
12 = 4 × 3
12 = 6 × 2

可以看到，后兩個乘積就是前面兩個反過來，反轉(zhuǎn)的分界點就在sqrt(n)。

換句話說，如果在[2,sqrt(n)]這個區(qū)間之內(nèi)沒有發(fā)現(xiàn)可整除因子，就可以直接斷定n是素數(shù)了，因為在區(qū)間[sqrt(n),n]也一定不會發(fā)現(xiàn)可整除因子。

這樣，isPrime函數(shù)的時間復(fù)雜度降為了 O(sqrt(N))，但是我們實現(xiàn)countPrimes函數(shù)其實并不需要這個函數(shù)，以上只是希望讀者明白sqrt(n)的含義，因為等會還會用到。

高效實現(xiàn) countPrimes

高效解決這個問題的核心思路是和上面的常規(guī)思路反著來：

首先從 2 開始，我們知道 2 是一個素數(shù)，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8… 都不可能是素數(shù)了。

然后我們發(fā)現(xiàn) 3 也是素數(shù)，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12… 也都不可能是素數(shù)了。

看到這里，你是否有點明白這個排除法的邏輯了呢？先看我們的第一版代碼：

int countPrimes(int n) {
    boolean[] isPrim = new boolean[n];
    // 將數(shù)組都初始化為 true
    Arrays.fill(isPrim, true);

    for (int i = 2; i < n; i++) 
        if (isPrim[i]) 
            // i 的倍數(shù)不可能是素數(shù)了
            for (int j = 2 * i; j < n; j += i) 
                    isPrim[j] = false;

    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;

    return count;
}

圖片來自 Wikimedia

如果上面這段代碼你能夠理解，那么你已經(jīng)掌握了整體思路，但是還有兩個細(xì)微的地方可以優(yōu)化。

首先，回想剛才判斷一個數(shù)是否是素數(shù)的isPrime函數(shù)，由于因子的對稱性，其中的 for 循環(huán)只需要遍歷[2,sqrt(n)]就夠了。這里也是類似的，我們外層的 for 循環(huán)也只需要遍歷到sqrt(n)：

for (int i = 2; i * i < n; i++) 
    if (isPrim[i]) 
        ...

除此之外，很難注意到內(nèi)層的 for 循環(huán)也可以優(yōu)化。我們之前的做法是：

for (int j = 2 * i; j < n; j += i) 
    isPrim[j] = false;

這樣可以把i的整數(shù)倍都標(biāo)記為false，但是仍然存在計算冗余。

比如i = 4時算法會標(biāo)記 4 × 2 = 8，4 × 3 = 12 等等數(shù)字，但是 8 和 12 已經(jīng)被i = 2和i = 3的 2 × 4 和 3 × 4 標(biāo)記過了。

我們可以稍微優(yōu)化一下，讓j從i的平方開始遍歷，而不是從2 * i開始：

for (int j = i * i; j < n; j += i) 
    isPrim[j] = false;

這樣，素數(shù)計數(shù)的算法就高效實現(xiàn)了。其實這個算法有一個名字，叫做 Sieve of Eratosthenes。看下完整的最終代碼：

int countPrimes(int n) {
    boolean[] isPrim = new boolean[n];
    Arrays.fill(isPrim, true);
    for (int i = 2; i * i < n; i++) 
        if (isPrim[i]) 
            for (int j = i * i; j < n; j += i) 
                isPrim[j] = false;

    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;

    return count;
}