1.描述
Description:
Count the number of prime numbers less than a non-negative number, n.
2.分析
3.代碼
int countPrimes(int n) {
if (n <= 1) return 0;
bool *isPrime = (bool*)malloc(n * sizeof(bool));
for (unsigned int i = 0 ; i < n; ++i)
isPrime[i] = true;
int root = sqrt(n);
for (unsigned int i = 2; i <= root; ++i) {
if (isPrime[i]) {
for (unsigned int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
int sum = 0;
for (unsigned int i = 2; i < n; ++i) {
if (isPrime[i]) ++sum;
}
free(isPrime);
isPrime = NULL;
return sum;
}
