Hide sidebar
leetcode/DSA courseSystem Design

Count Primes

Count Primes

MathSieve of Eratosthenes
MediumLeetCode #204
20 min

Problem Statement

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

Example

Example 1:

Input: n = 10

Primes less than 10:

2
3
5
7

Count: 4

Output: 4

Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Solution (Sieve of Eratosthenes)

A highly efficient way to count primes up to a number n is the Sieve of Eratosthenes. This algorithm works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2.

Algorithm Steps

  • Create a boolean array isPrime of size n and initialize all entries it as true.
  • Mark 0 and 1 as not prime.
  • Loop from 2 up to the square root of n.
  • If isPrime[i] is true, then it is a prime number.
  • For each prime number, iterate through its multiples and mark them as not prime.
  • Finally, count the number of true values in the isPrime array.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Initialize an array of size 20 to all true.
Count Primes Solution

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        
        for i in range(2, int(n**0.5) + 1):
            if is_prime[i]:
                for multiple in range(i*i, n, i):
                    is_prime[multiple] = False
                    
        return sum(is_prime)