Sieve of Eratosthenes: Finding All Primes

What is the Sieve of Eratosthenes?

The Sieve is a 2200-year-old algorithm for finding all prime numbers up to a given limit $N$. It works by systematically eliminating composite (non-prime) numbers.

Step-by-step: Find all primes up to 100

Step 1 — Write all numbers from 2 to 100. (1 is not prime.)

Step 2 — Start with 2 (the first prime). Cross out all multiples of 2 (except 2 itself): 4, 6, 8, 10, 12, ..., 100. These are all even numbers greater than 2.

Step 3 — Move to the next uncrossed number: 3 (prime). Cross out all multiples of 3: 6, 9, 12, 15, 18, 21, ... (some are already crossed from Step 2).

Step 4 — Next uncrossed: 5 (prime). Cross out multiples of 5: 10, 15, 20, 25, 30, ... (many already crossed).

Step 5 — Next uncrossed: 7 (prime). Cross out multiples of 7: 14, 21, 28, 35, 49, 63, 77, 91.

Step 6 — Next would be 11, but $11^2 = 121 > 100$. We're done! Every remaining uncrossed number is prime.

The primes up to 100

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97$

That's 25 primes below 100.

Why we stop at $\sqrt{N}$

If a composite number $n \leq N$ has a factor, at least one factor must be $\leq \sqrt{N}$. So after crossing out multiples of all primes up to $\sqrt{N}$, every remaining number must be prime. For $N = 100$: $\sqrt{100} = 10$, so we only need primes 2, 3, 5, 7.

Efficiency

The sieve is very efficient: for finding all primes up to $N$, it takes roughly $O(N \log \log N)$ operations — nearly linear. It's the fastest known method for generating a list of small primes.

Fun facts

• About 1 in every $\ln N$ numbers near $N$ is prime (Prime Number Theorem).
• The largest known prime (as of 2024) has over 41 million digits.
• There are infinitely many primes (proved by Euclid ~300 BC).

Try it in the visualization

Watch the 10×10 grid of numbers 1–100. Multiples of 2 are crossed first (red), then 3 (blue), then 5, then 7. Surviving numbers glow green — they're the primes. The animation shows why each step eliminates fewer numbers.