#204
Count Primes
Medium Sieve of Eratosthenes
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count the prime numbers strictly less than n.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how many primes are below n (n up to 5 million)?
Why this works: instead of testing each number, cross out the multiples of each prime. Every composite gets crossed out by its smallest prime factor.
Example: n = 10
start: 2 3 4 5 6 7 8 9p=2: cross 4, 6, 8p=3: cross 9left: 2 3 5 7 → 4 primes
✦Hints open one at a time
Checking each number by trial division is too slow for n up to 5 million.
Instead of testing numbers, cross out multiples of each prime.
Start crossing out from p * p — smaller multiples were already crossed out by smaller primes.
↗Approach
Sieve of Eratosthenes: a boolean array marks composites. For each p with p * p < n that is still unmarked, mark p*p, p*p+p, … as composite. Count what remains unmarked from 2 to n-1.
</>Solution (Java)
class Solution {
public int countPrimes(int n) {
if (n < 3) return 0;
boolean[] composite = new boolean[n];
for (int p = 2; (long) p * p < n; p++) {
if (composite[p]) continue;
for (int m = p * p; m < n; m += p) composite[m] = true; // cross out multiples
}
int count = 0;
for (int i = 2; i < n; i++) if (!composite[i]) count++;
return count;
}
}!Common mistake
Starting the inner loop at 2 * p (still correct, just slower) or using int for p * p, which can overflow — use p <= n / p or a long.
Complexity
- Time: O(n log log n).
- Space: O(n).
