Description:
Count the number of prime numbers less than a non-negative number, n
click to show more hints.
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
素数挑选法。
int countPrimes(int n) {
bool * IsPrime = (bool*)malloc(sizeof(bool) * n);
for (int i = 0; i < n; i++) IsPrime[i] = true;
for (int i = 2; i < n; i++) {
if (IsPrime[i]) {
for (int j = i + i; j < n; j += i) {
IsPrime[j] = false;
}
}
}
int ans = 0;
for (int i = 2; i < n; i++) if (IsPrime[i]) ans++;
free(IsPrime);
return ans;
}