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.

Description Hints 3 Solution Video 6:46

204. Count Primes

Medium35.8% acceptance17 companies

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⁶

Asked at 17 companies

Fast

Nokia NVIDIA Accenture Citadel Intel Epic Systems

Google Amazon Microsoft Bloomberg

TCS

+5 more

SAP Meta Uber Apple Goldman Sachs

Topics

Hints open one at a time

Hint 1

Checking all the integers in the range [1, n - 1] is not efficient. Think about a better approach.

Hint 2

Since most of the numbers are not primes, we need a fast approach to exclude the non-prime integers.

Hint 3

Use Sieve of Eratosthenes.

6:46

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution