Count Primes
Medium · Math · Array · Math · Enumeration · Number Theory
Problem
Given a whole number n, return how many prime numbers are strictly less than n.
A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, …. n itself is never counted, even when it is prime, and neither 0 nor 1 is prime.
n can be as large as 5,000,000. Testing each number on its own by trial division is too slow at that size; crossing off multiples, the Sieve of Eratosthenes, is the intended approach.
Examples
Input: n = 10 Output: 4
The primes below 10 are 2, 3, 5 and 7.
Input: n = 0 Output: 0
There are no primes below 0.
Input: n = 1 Output: 0
1 is not prime, and nothing below it is either.
Constraints
- 0 <= n <= 5 · 10^6
Approaches
- Baseline: trial division up to √k — time O(n√n), space O(1)
Follow-up
What if you need the primes in a window far from zero, such as between 10^12 and 10^12 + 10^6? Sieve only up to √(10^12) = 10^6 and cross off inside the window: the segmented sieve. And if the sieve stores each number’s smallest prime factor instead of a yes/no flag, it also factorizes any number up to n in O(log n). Both are use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
