## Algorithm

Problem Name: 204. Count Primes

Given an integer `n`, return the number of prime numbers that are strictly less than `n`.

Example 1:

```Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
```

Example 2:

```Input: n = 0
Output: 0
```

Example 3:

```Input: n = 1
Output: 0
```

Constraints:

• `0 <= n <= 5 * 106`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int countPrimes(int n) {
bool *flag = (bool *)calloc(n + 1, sizeof(bool));
int *prime = (int *)calloc(n / 2, sizeof(int));

flag[0] = 1;
flag[1] = 1;

int i, j;
int count = 0;
for (i = 2; i  <  n; i++) {
if (flag[i] == 0) { /* i is prime */
prime[count ++] = i;
}
for (j = 0; j  <  count && i * prime[j] < n; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) { /* important */
break;
}
}
}
return count;
}

int main() {

printf("%d\n", countPrimes(5000000));
return 0;
}
``````
Copy The Code &

Input

cmd
n = 10

Output

cmd
4

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const countPrimes = function (n) {
const memo = Array(n).fill(false)
let res = 0
for (let i = 2; i  <  n; i++) {
if (memo[i] === false) {
res++
for (let j = 2; i * j  <  n; j++) {
memo[i * j] = true
}
}
}

return res
}
``````
Copy The Code &

Input

cmd
n = 10

Output

cmd
4

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def countPrimes(self, n):
primes = [i for i in range(2, n)]
for i in range(2, n):
for prime in primes:
if i ** (prime - 1) % prime != 1 and prime > i:
primes.remove(prime)
return len(primes)
``````
Copy The Code &

Input

cmd
n = 0

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0204_CountPrimes
{
public int CountPrimes(int n)
{
var notPrime = new bool[n];
var count = 0;
for (int i = 2; i  <  n; i++)
{
if (!notPrime[i])
{
count++;
for (int j = 2; j * i  <  n; j++)
notPrime[i * j] = true;
}
}

return count;
}
}
}
``````
Copy The Code &

Input

cmd
n = 0