素数的定义看起来很简单，如果⼀个数只能被 1 和它本⾝整除，那么这个数就是素数。
返回区间 [2, n) 中有⼏个素数
1
2
3
4
// 返回区间 [2, n) 中有⼏个素数
int countPrimes(int n)
// ⽐如 countPrimes(10) 返回 4
// 因为 2,3,5,7 是素数
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim(i)) count++;
return count;
}
// 判断整数 n 是否是素数
boolean isPrime(int n) {
for (int i = 2; i < n; i++)
if (n % i == 0)
// 有其他整除因⼦
return false;
return true;
}
这样写的话时间复杂度 O(n^2)，问题很⼤
方法二
修改⼀下上⾯的 isPrim 代码中的 for 循环条件：
1
2
3
4
5
6
boolean isPrime(int n) {
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
// 有其他整除因⼦
return false;
}
如果在 [2,sqrt(n)] 这个区间之内没有发现可整除因⼦，就可以直接断定 n 是素数了，因为在区间 [sqrt(n),n] 也⼀定不会发现可整除因⼦
isPrime 函数的时间复杂度降为 O(sqrt(N))
方法三
⾼效解决这个问题的核⼼思路是和上⾯的常规思路反着来：
- ⾸先从 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
int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
// 将数组都初始化为 true
Arrays.fill(isPrim, true);
for (int i = 2; i < n; i++)
if (isPrim[i])
// i 的倍数不可能是素数了
for (int j = 2 * i; j < n; j += i)
isPrim[j] = false;
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim[i]) count++;
return count;
}
方法四
⾸先，回想刚才判断⼀个数是否是素数的 isPrime 函数，由于因⼦的对称性，其中的 for 循环只需要遍历 [2,sqrt(n)] 就够了。这⾥也是类似的，我们外层的 for 循环也只需要遍历到 sqrt(n) ：
内层的 for 循环也可以优化，⽐如 n = 25 ， i = 4 时算法会标记 4 × 2 = 8，4 × 3 = 12 等等数字，但是这两个数字已经被 i = 2 和 i = 3 的 2 × 4 和 3 × 4 标记了。我们可以稍微优化⼀下，让 j 从 i 的平⽅开始遍历，⽽不是从 2 * i 开始。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
// 将数组都初始化为 true
Arrays.fill(isPrim, true);
for (int i = 2; i * i < n; i++)
if (isPrim[i])
// i 的倍数不可能是素数了
for (int j = i * i; j < n; j += i)
isPrim[j] = false;
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim[i]) count++;
return count;
}
该算法的时间复杂度⽐较难算，显然时间跟这两个嵌套的 for 循环有关，其操作数应该是：
1
n/2 + n/3 + n/5 + n/7 + ... = n × (1/2 + 1/3 + 1/5 + 1/7...)
括号中是素数的倒数。其最终结果是 O(N * loglogN)
