Problem Statement
Sieve of Eratosthenes
You are given a number n. You need to count how many prime numbers are smaller than n. A prime number is a whole number bigger than 1 that can only be divided evenly by 1 and itself, like 2, 3, 5, and 7. A number that is not prime, like 4 or 6, is called composite, which just means it has other divisors. The trick we use here is called the Sieve of Eratosthenes. Think of it like a checklist of every number, where you cross out the ones that cannot be prime. You start with 2 (the smallest prime), cross out every multiple of 2 (4, 6, 8, and so on), then move to the next number that is still not crossed out, and repeat. Whatever survives the crossing-out is prime. The reason this fits the problem is that crossing out multiples is much faster than testing each number on its own, and it gives us the count in O(n log log n) time, which is nearly linear.
Signals to notice
Brute force first
Test each number for primality — O(n√n).
The key insight
Sieve of Eratosthenes: mark multiples of each prime starting from p². O(n log log n).
Trace it on n=10
init: isPrime=[F,F,T,T,T,T,T,T,T,T] (indices 0..9), loop i in range(2, int(sqrt(10))+1)=2..3 i=2: isPrime[2]=True -> mark j=4,6,8 (start i*i=4, step 2, <10): isPrime=[F,F,T,T,F,T,F,T,F,T] i=3: isPrime[3]=True -> mark j=9 (start i*i=9, step 3, <10): isPrime=[F,F,T,T,F,T,F,T,F,F] loop ends (i=4 -> 4>3) sum(isPrime): True at indices 2,3,5,7 -> count=4 return 4
What must stay true
Every composite has a prime factor ≤ √n. Marking multiples of primes up to √n eliminates all composites.
Shape of the loop
isPrime = [True]*n; isPrime[0]=isPrime[1]=False
for i from 2 while i*i < n:
if isPrime[i]:
for j from i*i to n step i:
isPrime[j] = False
return count(isPrime is True)Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Starting elimination from 2p instead of p² — smaller multiples already marked by prior primes.