JAVA算法：統計素數的數量

統計所有小于非負整數 n 的質數的數量。

示例:

輸入: 10

輸出: 4

解釋: 小于 10 的質數一共有 4 個, 它們是 2, 3, 5, 7 。

算法設計

用數組flag标記非素數，每當出現一個flag[i]為false，計數器count加一。

關于素數有三點：

1. 大于3的素數一定是奇數，如3，5，7；
2. 奇數中的非素數也一定是奇數的乘積。
3. 對于一個很大的數n，它的兩個因數i和j中一定有一個小于n的開方，是以我們讓i <= Math.sqrt(n)，j >= n，這樣可以避免重複讨論一些情況。

首先，我們用i從3到Math.sqrt(n)進行标記。

其次，根據上述的第2、3兩點，通過乘積i*j對應index的方法對在flag中對合數為index的值指派true，j+=2，外層一樣，i+=2，因為大于3的數中隻有奇數有可能是質數，而這些質數i可以通過j的循環标記所有i作為因數的合數。

标記完所有的合數之後，再用Math.sqrt(n)到n之間的周遊，count所有未被标記true的質數。

public int countPrimes(int n) {
       boolean[] mark = new boolean[n];
        if (n <= 2) return 0;
        int i = 3, count = 1; //i from 3, so there is one prime: 2
        while (i <= Math.sqrt(n)) {
            if (!mark[i]) {
                count++;
                int j = i;
                while (i*j < n) {
                    mark[i*j] = true;
                    j += 2;
                }
            }
            i += 2;
        }
        while (i < n) {
            if (!mark[i]) count++;
            i += 2;
        } 
        return count; 
}
           

另外一種算法設計

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] primes = new boolean[n];
        Arrays.fill(primes, true);
        for (int i = 2; i < n; i++) {
            for (int j = i+i; j < n; j += i) {
                primes[j] = false;
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (primes[i]) count++;
        }
        return count;
    }
}