*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #204 (*Easy*): Count Primes

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Count the number of prime numbers less than a non-negative number,

`n`

.

####
*Examples:*

*Examples:*

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:*

*Constraints:*

`0 <= n <= 5 * 10^6`

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

There are several ways to go about solving this problem, but the classic solution is known as the **sieve of Eratosthenes**. For the sieve of Eratosthenes, we start by creating a boolean array (**seen**) of size **n** to represent each of the numbers less than **n**.

We start at **2** and for each number processed (**num**), we iterate through and mark each multiple (**mult**) of **num**, starting at **num^2**, as seen. We start at **num^2** because every multiple up to the **num**'th multiple will have been guaranteed to have been seen before, since they're also a multiple of a smaller number. For example, when processing **5**s, we can skip to **25** because **10** will have been seen when we processed **2**s, **15** when we processed **3**s, and **20** when we processed **2**s.

Then we move **num** forward, skipping any numbers that have already been seen. By doing this, we will only stop on prime numbers, because they haven't been seen as a multiple of a previous iteration. We just have to update our count (**ans**) each time we stop and then **return ans** once we reach **n**.

( visual from the **wikipedia page on the sieve of Eratosthenes** )

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var countPrimes = function(n) {
let seen = new Uint8Array(n), ans = 0
for (let num = 2; num < n; num++) {
if (seen[num]) continue
ans++
for (let mult = num * num; mult < n; mult += num)
seen[mult] = 1
}
return ans
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def countPrimes(self, n: int) -> int:
seen, ans = [0] * n, 0
for num in range(2, n):
if seen[num]: continue
ans += 1
seen[num*num:n:num] = [1] * ((n - 1) // num - num + 1)
return ans
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int countPrimes(int n) {
boolean[] seen = new boolean[n];
int ans = 0;
for (int num = 2; num < n; num++) {
if (seen[num]) continue;
ans += 1;
for (long mult = (long)num * num; mult < n; mult += num)
seen[(int)mult] = true;
}
return ans;
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
int countPrimes(int n) {
vector<bool> seen(n, false);
int ans = 0;
for (int num = 2; num < n; num++) {
if (seen[num]) continue;
ans++;
for (long mult = (long)num * num; mult < n; mult += num)
seen[mult] = true;
}
return ans;
}
};
```

## Discussion (1)

Fixed an int overflow issue with the Java and C++ codes.