204 计数质数
什么是质数
质数是除了1和自己以外,不能被其他数整除的数
特别地,1不是质数,质数要求大于1
例如:
- 5 = 1 * 5,5是质数
- 6 = 1 * 6, 6 = 2 * 3,6能被2和3整除,6不是质数
如何判断质数
假设我们想知道x是不是质数,那么需要遍历所有比x小的自然数i(从2开始),如果存在x % i == 0说明存在不为1和自身的自然数,能被x整除,因此x不满足质数定义
如果遍历结束,都没有找到这么一个i,那么x就是质数
链接讲的非常清楚,我就不赘述了
class Solution {
public:
// 判断质数
bool isPrime(int k){
for(int i = 2; i < k; i++){
if(k % i == 0)
return false;
}
return true;
}
int countPrimes(int n) {
int count = 0;
for(int i = 2; i < n; i++){
if(isPrime(i))
count++;
}
return count;
}
};
可以进一步优化:
判断是否是质数时,不需要遍历所有小于x的元素,而是遍历小于sqrt(x)的元素
class Solution {
public:
int countPrimes(int n) {
// 因为素数筛选法判断的是「不是质数的数」,因此默认都是质数
vector<bool> isPrime(n + 1, true);
for(int i = 2; i < n; i++){
// 如果是质数,则根据该质数排除一系列不是质数的数
if(isPrime[i]){
// 从2 * i开始,3 * i, 4 * i等等都不是质数
for(int j = 2 * i; j < n; j += i){
isPrime[j] = false;
}
}
}
int count = 0;
for(int i = 2; i < n; i++){
if(isPrime[i]){
count++;
}
}
return count;
}
};
可以进一步优化:
class Solution {
public:
int countPrimes(int n) {
vector<bool> isPrime(n + 1, true);
// *优化1
// 由对称性可知,判断质数不需要遍历所有小于n的i
// 只需要遍历[2, sqrt(n)]
for(int i = 2; i * i < n; i++){
if(isPrime[i]){
// *优化2
// 避免例如2 * 5 和 5 * 2的重复,j从i * i开始
for(int j = 2 * i; j < n; j += i){
isPrime[j] = false;
}
}
}
int count = 0;
for(int i = 2; i < n; i++){
if(isPrime[i]){
count++;
}
}
return count;
}
};