204. Count Primes LeetCode Solution

In this guide, you will get 204. Count Primes LeetCode Solution with the best time and space complexity. The solution to Count Primes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Primes solution in C++
Count Primes solution in Java
Count Primes solution in Python
Additional Resources

204. Count Primes LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(n\log(\log n))
Space Complexity: O(n)

204. Count Primes LeetCode Solution in C++

class Solution {
 public:
  int countPrimes(int n) {
    if (n <= 2)
      return 0;
    const vector<bool> isPrime = sieveEratosthenes(n);
    return ranges::count(isPrime, true);
  }

 private:
  vector<bool> sieveEratosthenes(int n) {
    vector<bool> isPrime(n, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i * i < n; ++i)
      if (isPrime[i])
        for (int j = i * i; j < n; j += i)
          isPrime[j] = false;
    return isPrime;
  }
};
/* code provided by PROGIEZ */

204. Count Primes LeetCode Solution in Java

class Solution {
  public int countPrimes(int n) {
    if (n <= 2)
      return 0;
    final boolean[] isPrime = sieveEratosthenes(n);
    int ans = 0;
    return (int) IntStream.range(0, isPrime.length)
        .mapToObj(i -> isPrime[i])
        .filter(p -> p)
        .count();
  }

  private boolean[] sieveEratosthenes(int n) {
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i * i < n; ++i)
      if (isPrime[i])
        for (int j = i * i; j < n; j += i)
          isPrime[j] = false;
    return isPrime;
  }
}
// code provided by PROGIEZ

204. Count Primes LeetCode Solution in Python

class Solution:
  def countPrimes(self, n: int) -> int:
    if n <= 2:
      return 0
    return sum(self._sieveEratosthenes(n))

  def _sieveEratosthenes(self, n: int) -> list[bool]:
    isPrime = [True] * n
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n**0.5) + 1):
      if isPrime[i]:
        for j in range(i * i, n, i):
          isPrime[j] = False
    return isPrime
 # code by PROGIEZ