labuladong 题解思路 难度中等
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：0
class Solution {
public:
bool is_primes(int k) {
for(int i = 2;i <= sqrt(k);i++){
if (k%i==0) {
return false;
}
}
return true;
}
int countPrimes(int n) {
int cnt = 0;
for(int i =2;i <n;i++) {
cnt+= is_primes(i)?1:0;
}
return cnt;
}
};
class Solution {
public:
int countPrimes(int n) {
int cnt = 0;
vector<bool> is_primes (n,true);
for(int i = 2; i <= sqrt(n);i++) {
for(int j = 2; j*i <n;j++) {
is_primes[j*i] = false;
}
}
for(int i =2;i <n;i++) {
cnt+= is_primes[i]?1:0;
}
return cnt;
}
};
标签：204,示例,int,质数,计数,primes,public From： https://www.cnblogs.com/zle1992/p/16652422.html