204. 计数质数
描述
示例
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
思路
- 一次判断从2~n质数的数量返回，核心算法转换为判断一个数是否为质数。
- 根据质数的字面定义，一个数只能被1和自身整除即为质数，可以2~m-1依次求余，为0则不为质数。
- 优化点：可以不必从2~m-1，只需遍历2 ~ √m.因为如果m能被2 ~ m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。例如16能被2,4,8整除，16=28,2小于4,8大于4，16=44,4=√16，因此只需判定在2~4之间有无因子即可。
-
上述方案实现正确，但是超过了预期时间。简单估算一下，大约是O(n*n)级别的复杂度。优化方向是利用空间换时间，维持一个大小为n的bool型数组，当x判断完毕后，把数组内所有x的倍数都置位false，每次判断一个数是否为质数时先查表，表里面有才遍历。
- 最优解：埃拉托斯特尼筛法(参考)
- 一个数如果在遍历到它的时候都没有被标记，则证明在1~m-1的区间内没有能够整除它的数，所以这个数一定是一个质数
- 只需遍历1~√n，大于√n的数如果没有遍历到一定是质数，且也不需要将后续的倍数标记，因为√n*√n >= n
class Solution_204_01 {
public:
int countPrimes(int n) {
int cnt = 0;
for (int i = 2; i < n; ++i) {
if (isPrime(i)) ++cnt;
}
return cnt;
}
bool isPrime(int m) {
for (int i = 2; i <= sqrt(m); ++i) {
if (m % i == 0) return false;
}
return true;
}
};
class Solution_204_02 {
public:
int countPrimes(int n) {
bool pArray[n + 1] = {0};
int cnt = 0;
for (int i = 2; i < n; ++i) {
if (!pArray[i] && isPrime(i)) {
++cnt;
for (int j = i; j < n; j += i) pArray[j] = true;
}
}
return cnt;
}
bool isPrime(int m) {
for (int i = 2; i <= sqrt(m); ++i) {
if (m % i == 0) return false;
}
return true;
}
};
class Solution_204_03 {
public:
int countPrimes(int n) {
bool notPrime[n+1] = {0};
int cnt = 0, limit = sqrt(n);
for (int i = 2; i <= limit; ++i) {
if (!notPrime[i]) {
for (int j = i * i; j < n; j += i) {
notPrime[j] = true;
}
}
}
for (int i = 2; i < n; ++i) {
if (!notPrime[i]) ++cnt;
}
return cnt;
}
};
