题目大意
统计所有小于非负整数 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%。
