Count Primes
Medium· sieve· primes
Problem
Given an integer n, return how many prime numbers are strictly less than n. Testing each number individually for primality is too slow at the upper limit.
Examples
Input: n = 10
Output: 4
2, 3, 5 and 7.
Input: n = 0
Output: 0
Constraints
- • 0 <= n <= 5·10^6
Hints & approach
Hint 1
Instead of testing numbers, cross out the ones that cannot be prime.
Hint 2
Every multiple of a prime p (other than p) is composite.
Hint 3
Start crossing out at p·p and only loop p up to √n.
Approachtry the hints first
Use the Sieve of Eratosthenes. Allocate a boolean array of size n marked prime, then clear 0 and 1. For each p from 2 while p·p < n, if p is still marked, mark p·p, p·p + p, … as composite; smaller multiples were already removed by smaller primes. Count the entries still marked.
Time O(n log log n) · Space O(n)