题目大意

统计所有小于非负整数 n 的质数的数量。
示例：

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

思路

本质上是一个优化求判断素数的问题，这里只介绍两种高效的算法。

方法一：6的倍数

自然数可以表示为6x , 6x+1, 6x+2, 6x+3, 6x+4, 6x+5这六类。其中：6x , 6x+2, 6x+3, 6x+4一定不是质数，那么质数只有可能出现在6x+1和6x+5(即6x-1)之中。

public int countPrimes(int n) {
        int res = 0;
        for(int i=2;i<n;i++)
            res += isPrime(i);
        return res;   
    }
private int isPrime(int n) {
        if(n==2 || n==3) return 1;
        if(n%6!=1 && n%6!=5) return 0; //不在6的两侧
        for(int i =5;i<=Math.sqrt(n);i+=6) 
            if(n%i==0 || n%(i+2)==0) return 0;
        return 1;
    }

运行时间398ms, 5.98%。

方法二：厄拉多塞筛法

image.png

image.png

image.png

image.png

步骤：
1.将1-N这些数依次放入一张表中，然后遍历这张整数表。
2.如果当前这个数没有被圈出，圈出它，并且将它的倍数全部圈出。
3.遍历下一个数，重复步骤2，直至这张整数表遍历完毕。

 public int countPrimes(int n) {
        boolean[] sign = new boolean[n];
        int cnt =0;
        for(int i=2;i<n;i++) {
            if(!sign[i]){
                ++cnt;
                for(int j=2;i*j<n;++j)
                    sign[i*j] = true;  //不是质数
            }
        }
        return cnt;
    }

运行时间34ms 55.71%。