網頁

2018/12/23

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(N2),當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;
}

沒有留言:

張貼留言