Number Theory · 162Medium
Count Primes
Given an integer n, return the number of prime numbers strictly less than n.
Constraints
- 0 <= n <= 5 * 10^6
Examples
countPrimes(10) -> 4 // 2, 3, 5, 7 countPrimes(0) -> 0 countPrimes(2) -> 0 // strictly less than n countPrimes(1) -> 0 countPrimes(3) -> 1 // only 2 countPrimes(100) -> 25
Edge cases
- n = 0, 1 and 2 all return 0.
- The bound is STRICT — n itself is never counted.
Show the target complexity (spoiler)
- Naive
- O(n * sqrt(n)) time — test each number for primality by trial division. Too slow at n
- Target
- O(n log log n) time, O(n) space — the Sieve of Eratosthenes, marking multiples of each prime starting from its square.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/22-number-theory/162-count-primes.js ./practice c 162