[LeetCode] #204 计数质数

问题描述：
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

这是一道简单题，但是却并没有那么直接的简单。

枚举暴力法是肯定不行的，时间效率太低。于是介绍解决这个问题的一个著名算法--Eratosthenes筛选法。

来自 https://www.cnblogs.com/color-my-life/p/3265236.html 的解释，我觉得非常通俗易懂。
首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设A * B = N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到这个数可以整除N。
不过在程式中使用开根号会精确度的问题，所以可以使用 i*i <= N进行检查，且执行更快 。
再来假设有一个筛子存放1～N，例如：
2 3 4 5 6 7 8 9 10 11 12 ........N
先将2的倍数筛去：
2 3 5 7 9 11 13........N
再将3的倍数筛去：
2 3 5 7 11 13 17 19........N
再来将5的倍数筛去，再来将7的质数筛去，再来将11的倍数筛去........，如此进行到最后留下的数就都是质数，这就是Eratosthenes筛选方法（Eratosthenes Sieve Method）
检查的次数还可以再减少，事实上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍数，使得程式中的if的检查动作可以减少。

class Solution {
    public int countPrimes(int n) {
        int count = 0;
        int i;
        boolean[] b = new boolean[n];
        for (i = 2; i < n; i++)
            b[i] = true;
        i = 2;
        while (i * i < n) {
            if (b[i]) {
                count++;
                int k = 2 * i;
                while (k < n) {
                    b[k] = false;
                    k += i;
                }
            }
            i++;
        }
        while (i < n) {
            if (b[i])
                count++;
            i++;
        }
        return count;
    }
}

几乎相同的算法，更好看的写法(理论上效率应该比上面那个要低一点点)

class Solution {
    public int countPrimes(int n) {
        int count = 0;
        boolean[] booleans = new boolean[n];
        for (int i = 2; i < n; i++) {
            if(!booleans[i]){
                count++;
                for (int j = i; j < n; j=j+i) {
                    booleans[j] = true;
                }
            }
        }
        return count;
    }
}

[LeetCode] #204 计数质数

原文：https://www.cnblogs.com/caophoenix/p/11354348.html