blob: 7d02add0c0d0e401d8424c2a70b735745df5847b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
// 204. Count Primes
#include "leetcode.h"
/*
* given an integer 'n', return the number of prime numbers that are strictly
* less than 'n'.
*/
int countPrimes(int n) {
if (n < 2)
return 0;
if (n == 3)
return 1;
bool *table = (bool *)calloc(n, sizeof(bool));
table[0] = table[1] = 1;
for (int i = 2; i <= sqrt(n); i++) {
if (table[i])
continue;
for (int j = i * i; j < n; j += i)
table[j] = 1;
}
int ans = 0;
for (int i = 2; i < n; i++)
if (!table[i])
ans++;
free(table);
return ans;
}
int main() {
printf("%d\n", countPrimes(10)); // expect: 4
printf("%d\n", countPrimes(0)); // expect: 0
printf("%d\n", countPrimes(1)); // expect: 0
}
|