Count Prime Numbers — Sieve of Eratosthenes
Solve this Problem
You're handed a single non-negative integer
n. Your task: count how many primes live in the range below it — every prime p with p < n.
Checking each candidate's primality independently repeats the same work over and over — the Sieve of Eratosthenes instead crosses off composites in bulk: once a number i is confirmed prime, every multiple of i starting at i² is guaranteed composite and can be marked in one pass, with no divisor checks needed for any of them individually.
Test Case 1:
Input:n = 10
Output:4
Explanation:The primes strictly less than 10 are 2, 3, 5, 7 — four of them.
Test Case 2:
Input:n = 0
Output:0
Explanation:There are no numbers at all below 0.
Test Case 3:
Input:n = 1
Output:0
Explanation:The only candidate below 1 is nothing — no primes possible.
Constraints
- ◆
0 ≤ n ≤ 5 × 10⁶
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Trial Division per Number
BruteTest every number from 2 up to n - 1 individually, checking primality by trial division up to its own square root. Each check costs O(√k), and there are up to n of them — correct, but a lot of duplicated work, since the same small primes get re-tested as divisors again and again for every candidate.
Time
O(n√n)Space
O(1) extraJava
1class Solution {
2 public int countPrimes(int n) {
3 int count = 0;
4 for (int num = 2; num < n; num++) {
5 if (isPrime(num)) {
6 count++;
7 }
8 }
9 return count;
10 }
11
12 private boolean isPrime(int num) {
13 for (long i = 2; i * i <= num; i++) {
14 if (num % i == 0) {
15 return false;
16 }
17 }
18 return true;
19 }
20}Optimal — Sieve of Eratosthenes
OptimalInstead of testing each number from scratch, mark composites in bulk: for every unmarked number i starting at 2, every multiple of i starting at i² is composite (anything smaller was already caught by a smaller prime factor). One pass builds the full picture — no number is ever tested for primality by trial division at all.
Time
O(n log log n)Space
O(n)Java
1class Solution {
2 public int countPrimes(int n) {
3 if (n < 3) return 0;
4 boolean[] composite = new boolean[n];
5 int count = 0;
6 for (int i = 2; i < n; i++) {
7 if (!composite[i]) {
8 count++;
9 for (long j = (long) i * i; j < n; j += i) {
10 composite[(int) j] = true;
11 }
12 }
13 }
14 return count;
15 }
16}