解题思路：
一般判定素数的方法就是下面这个函数：1
2
3
4
5
6
7boolean isPrime(int x){
if(x<2) return false;
for(int i = 2;i*i<=x;i++){
if(x % i == 0) return false;
}
return true;
}
但是这个函数在判断范围内素数时，会出现重复计算，造成超时，所以下面代码借鉴了labuladong大佬的思路:
“首先从 2 开始，我们知道 2 是一个素数，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8… 都不可能是素数了。
然后我们发现 3 也是素数，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12… 也都不可能是素数了。”
而且用数组把每次算出的值保存下来，避免重复计算。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public int countPrimes(int n) {
if(n <= 2) return 0;
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime,true);
for(int i = 2;i*i<=n;i++){
if(isPrime[i]){
for(int j = i * i;j<n;j+=i){
isPrime[j] = false;
}
}
}
int count = 0;
for(int i = 2;i<n;i++){
if(isPrime[i]) count++;
}
return count;
}
