Solution: Count Primes

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:

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

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

---

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:

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

---

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 5s, we can skip to 25 because 10 will have been seen when we processed 2s, 15 when we processed 3s, and 20 when we processed 2s.

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:

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

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

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

(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;
    }
};

Comments

[seanpgallivan]

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