medium
Count Primes
Given an integer n, return the number of prime numbers strictly less than n.
Constraints
- 0 ≤ n ≤ 5 · 10^6
Examples
in: n = 10
out: 4
2, 3, 5, 7.
Recognition clues
- All primes below a bound at once
- Testing each number individually costs O(n √n)
- Cross out multiples of each prime — sieve
Pattern
Math & Number TheoryAn answer "modulo a prime" says intermediate values overflow and you must reduce at every step, and that division becomes multiplication by a modular inverse. Bounds like 10^18 rule out iteration and point to O(log n) exponentiation or Euclid; "all primes up to n" is a sieve.
Solution
Create a boolean array marking every number from 2 to n - 1 as potentially prime. For each p from 2 while p · p < n, if p is still marked, cross out p·p, p·p + p, … (multiples below p·p were already removed by smaller primes). Count the survivors. The total crossing-out work is the harmonic sum over primes, which is O(n log log n).
time O(n log log n)space O(n)
Alternative approaches
- Trial division per number is O(n √n). A segmented or linear sieve reduces memory or hits O(n); Meissel–Lehmer counts primes without enumerating them.
Code it yourself
Solve in
Hints: