Skip to main content
Talentd

Count Primes - Solution & Explanation

MediumArrayMathEnumerationNumber Theory15 min readAsked at: Amazon, Microsoft, Apple +14
Practice this problem

Problem Statement

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

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.

This implementation uses a boolean array to keep track of prime numbers. We initialize the array assuming all numbers are prime, then use the Sieve of Eratosthenes method to mark non-prime numbers. Finally, we count the number of prime numbers remaining unmarked up to n.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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.

This solution implements a naive primality test, evaluating the primality of each number up to n. For each number, divisibility is tested up to the square root to determine if it is prime. Though simple, this method is not optimized for large input values.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoJavaScriptC#

Python

Java

C++

Go

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Primality TestO(n * sqrt(n))O(1)Good for learning prime checks or when n is very small
Sieve of EratosthenesO(n log log n)O(n)Best choice for counting primes in a range efficiently

Video Solution

Count Primes • Kevin Naughton Jr. • 61,198 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Primes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Count of Numbers Which Are Not Special

Next

Number of Common Factors