题目描述
统计所有小于非负整数 n 的质数的数量。
样例
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
C++ 代码
class Solution {
public:
// 暴力解
/*
首先 6x 肯定不是质数,因为它能被 6 整除;其次 6x+2 肯定也不是质数,因为它还能被2整除;
依次类推,6x+3 肯定能被 3 整除;6x+4 肯定能被 2 整除。
那么,就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。
所以循环的步长可以设为 6,然后每次只判断 6 两侧的数即可。
*/
bool isPrime(int num)
{
if (num <= 3) {
return num > 1;
}
// 不在6的倍数两侧的一定不是质数
if (num % 6 != 1 && num % 6 != 5) {
return false;
}
int sqrts = sqrt(num);
for (int i = 5; i <= sqrts; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
int countPrimes(int n) {
int cnt = 0;
for(int i = 1; i < n; ++i)
{
if(isPrime(i)) {cnt++;};
}
return cnt;
}
};