LeetCode Count Primes 數質數

本篇為LeetCode上演算法的簡單問題，Count Primes 數質數。

題目如下：

Count the number of prime numbers less than a non-negative number, n.

Example:

Input:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

輸入一正整數n，計算小於n的整數中有多少個質數(prime)。

所謂的質數是指大於1且只能被1和自己整除的整數。而依照此定義想到的解法如下。

public static int countPrimes3(int n) {
    if(n < 2) {                           // 負數，0，1不考慮
        return 0; 
    }
    n = n - 1;                            // 只算小於n的質數

    int primeCount = 0;                   // 質數計數
    for (int i = 2; i < n; i++) {         // 被除數，從2開始
        int divisibleCount = 0;           // 被整除的次數
        for (int j = 2; j < n; j++) {     // 除數，從2開始
            if (i % j == 0) {             // 被除數除以除數餘數若為0  
                divisibleCount++;         // 被整除的次數 + 1
            }
        }
        if(divisibleCount == 1) {         // 當被整除的次數只有1次，代表目前的被除數只能被自己整除
            primeCount++;                 // 質數計數 + 1
        }

    }
    return primeCount;
}

但效率極差，根本無法通過LeetCode的時間限制，因為時間複雜度為O(N²)，當N = 10,000時，代表直行次數為100,000,000（1億）次。

參考別人的答案如下

public static int countPrimes(int n) {
    if(n < 3) {
        return 0;
    }
    int primeCount = 0;
    boolean[] nonPrimes = new boolean[n];               // 用來記錄非質數的陣列
    for (int i = 2; i < n; i++) {        
        if(nonPrimes[i]) {                              // 整數i是否為質數?若是則跳過
            continue;
        }
        primeCount++;                                   // 若不是質數次數 + 1
        for (long j = (long)i * i; j < n; j += i) {  // 整數i自乘的數必為非質數，且自乘數i2 + i*n也仍為非質數 
            nonPrimes[(int) j] = true;
        }
    }

    return primeCount;
}

在上面的內迴圈中，從2開始自乘取得每個非質數並放入記錄非質數的陣列中，
當i=2時，分別得到4, 6, 8, 10, ... , n - 2；
當i=3時，分別得到9, 12, 15, 18, ... , n - 3；
...
而在外迴圈又會先判斷非質數陣列中某整數i是否存在，若存在代表i為非質數，則不繼續執行內迴圈。

改善一下，只要是2的倍數都是非質數，所以直接略過不考慮，如此內迴圈的執行次數至少就減少了一半。

public static int countPrimes(int n) {
    if (n < 3) {
        return 0;
    }
    int count = 1;                        // 先算入整數2
    boolean[] nonPrimes = new boolean[n];
    for (int i = 3; i < n; i += 2) {      // 不考慮2的倍數

        if (nonPrimes[i]) {
            continue;
        }
        count++;
        for (long j = (long) i * i; j < n; j += i) {
            nonPrimes[(int) j] = true;
        }
    }
    return count;
}

更快的寫法如下。

public static int countPrimes6(int n) {
    if (n < 3) {
        return 0;
    }
    int count = n / 2;
    boolean[] nonPrimes = new boolean[n];
    for (int i = 3; i * i < n; i += 2) {
        if (nonPrimes[i]) {
            continue;
        }
        for (long j = (long) i * i; j < n; j += 2 * i) {
            if (!nonPrimes[(int) j]) {
                --count;
                nonPrimes[(int) j] = true;
            }
        }
    }
    return count;
}