// 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 }