aboutsummaryrefslogtreecommitdiff
path: root/count_primes.c
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
}