[leetcode]204. Count Primes
Analysis
weekends~—— [好穷啊，吃不起鸡了~]
Count the number of prime numbers less than a non-negative number n. 计算小于n的数中有多少质数，不要想着一个个判断，还是那句话，暴力AC是不可能的，这辈子都不可能！
Implement
class Solution {
public:
int countPrimes(int n) {
bool *isPrime = new bool[n];
for(int i=
2; i<n; i++)
isPrime[i] = true;
for(int i=
2; i*i<n; i++){
if(!isPrime[i])
continue;
for(int j=i*i; j<n; j+=i)
isPrime[j] = false;
}
int cnt =
0;
for(int i=
2; i<n; i++){
if(isPrime[i])
cnt++;
}
return cnt;
}
};
下面是判断质数的一个函数，存一下，嘻嘻~
bool isPrime(int num){
if(num <=
1)
return false;
for(int i=
2; i*i<=num; i++){
if(num%i ==
0)
return false;
}
return true;
}
