【每日算法Day 83】计数质数
Wallace Xu 2020-08-22 算术
# LeetCode 204. 计数质数 (opens new window)
# 题目描述
统计所有小于非负整数 n 的质数的数量。
# 示例
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
1
2
3
2
3
# 解题思路
看到题目可能直接想到对于2~n的所有的数，检查其是否为质数。检查的方法大概为：
private boolean isPrime(int n){
for(int i = 2; i < n; i++){
if(n % i == 0) return false;
}
return true;
}
1
2
3
4
5
6
2
3
4
5
6
这样做的时间复杂度为O(n^2)，并且有很多重复的计算，通过将循环的搜索范围将为2~sqrt(n)可以将时间复杂度将为O(nlogn)。
可以通过使用额外O(n)的数组保存已经得出的数是否为素数来降低时间复杂度，如果一个数是素数i那么将其所有的小于n的倍数设为合数（如果一个数是合数，那么它的倍数一定在之前就被设置过了）。可以做一些小优化，例如外层循环仍然只需要从2找到根号n（复杂度降到logn），内层循环从i^2开始（不能从根本上降低复杂度）。该算法的时间复杂度为O(nloglogn)。
public int countPrimes(int n) {
if (n < 2) return 0;
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
int root = (int) Math.sqrt(n);
for (int i = 2; i <= root; 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++) {
count += isPrime[i] ? 1 : 0;
}
return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
另外还有埃拉托斯特尼筛法，具体内容就是： 要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
进一步可以理解为：要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的奇数倍剔除，剩下的奇数就是素数。
public int countPrimes(int n) {
if (n < 3) return 0;
int count = 1, root = (int) Math.sqrt(n);
boolean[] isPrime = new boolean[n];
for (int i = 3; i < n; i += 2) {
if (!isPrime[i]) {
if (i <= root) {
for (int j = i; j * i < n; j += 2)
isPrime[i*j]=true;
}
count++;
}
}
return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15