204. Count Primes - Solution & Explanation

The problem

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 * 10⁶

Approach overview

Problem Overview: Given an integer n, return the number of prime numbers strictly less than n. A prime number is greater than 1 and divisible only by 1 and itself. The challenge is efficiently identifying primes in the range [2, n) without repeatedly performing expensive divisibility checks.

Approach 1: Naive Primality Test (O(n * sqrt(n)) time, O(1) space)

The straightforward method checks each number from 2 to n - 1 and determines whether it is prime. For each number i, iterate from 2 up to sqrt(i) and check if any value divides it evenly. If no divisor exists, the number is prime and the counter increments. The key observation is that factors appear in pairs, so checking beyond sqrt(i) is unnecessary. This approach is easy to implement and useful for understanding the definition of primes, but it becomes slow when n grows large because you repeat divisibility checks for every number.

Approach 2: Sieve of Eratosthenes (O(n log log n) time, O(n) space)

The Sieve of Eratosthenes avoids repeated primality checks by eliminating multiples of known primes. Create a boolean array isPrime of size n initialized to true. Start from 2. If isPrime[i] is true, the number is prime and all multiples of i must be composite. Mark every multiple starting from i * i as false (i * i avoids redundant work because smaller multiples were already handled by previous primes). Continue this process until i * i >= n. Finally, count the indices that remain true. This technique transforms repeated divisibility checks into systematic marking using an array, dramatically improving performance for large ranges.

The algorithm relies on number theory properties: every composite number has a prime factor less than or equal to its square root. Once multiples of smaller primes are removed, remaining numbers must be prime. The approach is a classic example from math and number theory, and it appears frequently in problems involving prime generation, factorization, or divisor counting.

Recommended for interviews: Interviewers expect the Sieve of Eratosthenes. The naive method demonstrates you understand how primality works, but the sieve shows algorithmic optimization and awareness of classic enumeration techniques. For constraints up to millions, the sieve’s O(n log log n) time complexity scales efficiently while keeping the implementation simple.

Approach 1: Sieve of Eratosthenes

The Sieve of Eratosthenes is a classic algorithm to find all prime numbers up to a given limit. It efficiently marks non-prime numbers in a boolean array, allowing us to count the prime numbers left unmarked.

It operates by marking the multiples of each prime starting from 2, the smallest prime. This optimization significantly reduces the number of operations needed compared to checking each number individually.

Python

def count_primes(n):
    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 j in range(i * i, n, i):
                is_prime[j] = False
    return sum(is_prime)

print(count_primes(10))  # Output: 4

Java

import java.util.Arrays;

public class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = 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;
                }
            }
        }
        int count = 0;
        for (boolean prime : isPrime) {
            if (prime) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countPrimes(10));  // Output: 4
    }
}

C++

#include <iostream>
#include <vector>

int countPrimes(int n) {
    if (n <= 2) return 0;
    std::vector<bool> isPrime(n, true);
    isPrime[0] = 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 std::count(isPrime.begin(), isPrime.end(), true);
}

int main() {
    std::cout << countPrimes(10) << std::endl;  // Output: 4
    return 0;
}

JavaScript

function countPrimes(n) {
    if (n <= 2) return 0;
    const isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime.reduce((count, prime) => count + (prime ? 1 : 0), 0);
}

console.log(countPrimes(10));  // Output: 4

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

int countPrimes(int n) {
    if (n <= 2) return 0;
    bool isPrime[n];
    for (int i = 0; i < n; i++) isPrime[i] = true;
    isPrime[0] = 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;
            }
        }
    }
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

int main() {
    printf("%d\n", countPrimes(10));  // Output: 4
    return 0;
}

using System;

public class Solution {
    public int CountPrimes(int n) {
        if (n <= 2) return 0;
        bool[] isPrime = new bool[n];
        Array.Fill(isPrime, true);
        isPrime[0] = 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;
                }
            }
        }
        int count = 0;
        foreach (bool prime in isPrime) {
            if (prime) count++;
        }
        return count;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountPrimes(10));  // Output: 4
    }
}

Python's implementation relies on list comprehension and the sum function to efficiently count prime numbers. The Sieve of Eratosthenes is applied similarly to other language solutions, demonstrating Python's elegant handling of list operations.

Complexity

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

Try this approach in the editor

Approach 2: Naive Primality Test

A more basic approach to this problem is to check each number individually for primality. This involves testing each number for factors up to its square root. While less efficient than the sieve, it provides an instructive example of brute force in algorithm design.

Python

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

def count_primes(n):
    count = 0
    for i in range(2, n):
        if is_prime(i):
            count += 1
    return count

print(count_primes(10))  # Output: 4

Java

public class Solution {
    public boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    }

    public int countPrimes(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countPrimes(10));  // Output: 4
    }
}

C++

#include <iostream>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime(i)) count++;
    }
    return count;
}

int main() {
    std::cout << countPrimes(10) << std::endl;  // Output: 4
    return 0;
}

JavaScript

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;
    for (let i = 5; i * i <= n; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }
    return true;
}

function countPrimes(n) {
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime(i)) count++;
    }
    return count;
}

console.log(countPrimes(10));  // Output: 4

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime(i)) count++;
    }
    return count;
}

int main() {
    printf("%d\n", countPrimes(10));  // Output: 4
    return 0;
}

using System;

public class Solution {
    public bool IsPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    }

    public int CountPrimes(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (IsPrime(i)) count++;
        }
        return count;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.CountPrimes(10));  // Output: 4
    }
}

In Python, the naive solution applies a similar is_prime function, utilizing trial division to assess the primality of each number less than n. Despite being less efficient, it demonstrates a straightforward necessity for optimization with larger inputs.

Complexity

Time Complexity: O(n√n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Default Approach

func countPrimes(n int) int {
	primes := make([]bool, n)
	for i := range primes {
		primes[i] = true
	}
	ans := 0
	for i := 2; i < n; i++ {
		if primes[i] {
			ans++
			for j := i + i; j < n; j += i {
				primes[j] = false
			}
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sieve of Eratosthenes	Time Complexity: O(n log log n) Space Complexity: O(n)
Naive Primality Test	Time Complexity: O(n√n) Space Complexity: O(1)
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Naive Primality Test	O(n * sqrt(n))	O(1)	Good for learning prime checks or when n is very small
Sieve of Eratosthenes	O(n log log n)	O(n)	Best choice for counting primes in a range efficiently

Frequently asked questions

Is Count Primes easy or hard?

Count Primes is considered a medium difficulty problem. The logic of identifying primes is simple, but recognizing and implementing the Sieve of Eratosthenes efficiently is the key insight that raises it above beginner-level questions.

How to solve Count Primes in O(n)?

The standard solution is the Sieve of Eratosthenes, which runs in O(n log log n) time—very close to linear for practical input sizes. It works by iteratively marking multiples of primes in a boolean array starting from i*i, avoiding redundant divisibility checks.

What is the best approach for Count Primes?

The Sieve of Eratosthenes is the most efficient and widely expected approach. It marks multiples of each prime number in a boolean array and leaves only primes unmarked. The algorithm runs in O(n log log n) time with O(n) space, which is significantly faster than checking each number individually.

What data structure is used in Count Primes?

Most optimal implementations use a boolean array (or bitset) to track whether each number is prime. The array allows constant-time marking of composite numbers while iterating through multiples of each prime candidate.

What is the time complexity of Count Primes?

The optimal Sieve of Eratosthenes solution runs in O(n log log n) time and uses O(n) space for the boolean array that tracks prime candidates. A naive primality check approach requires O(n * sqrt(n)) time because each number must be tested against possible divisors.

Count Primes Python or Java solution approach?

Python and Java solutions typically implement the Sieve of Eratosthenes. Create a boolean array of size n, iterate from 2 up to sqrt(n), and mark multiples starting at i*i as non-prime. After processing, count the indices still marked true.

Is Count Primes asked at Google, Amazon, or Meta?

Count Primes is a common interview-style problem that appears in technical screens and coding practice sets used by companies like Google, Amazon, and Meta. It tests knowledge of prime numbers, algorithm optimization, and familiarity with classic techniques such as the Sieve of Eratosthenes.

Count Primes solution and explanation

The problem

Approach overview

Approach 1: Sieve of Eratosthenes

Approach 2: Naive Primality Test

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Primes solution and explanation

The problem

Approach overview

Approach 1: Sieve of Eratosthenes

Approach 2: Naive Primality Test

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems