Sieve of Eratosthenes — Definition, Formula & Examples

The Sieve of Eratosthenes is a simple algorithm that finds all prime numbers up to any limit you choose by repeatedly crossing out multiples of each prime, starting from 2.

Given a positive integer $n \geq 2$ , the Sieve of Eratosthenes iteratively marks as composite every multiple $kp$ (where $k \geq 2$ ) of each successive unmarked integer $p \leq \sqrt{n}$ , beginning with $p = 2$ . The integers that remain unmarked after all iterations are exactly the primes in the set $\{2, 3, \dots, n\}$ .

How It Works

Write down every integer from 2 to your chosen limit

n

. Start with the first number, 2, and cross out all of its multiples (4, 6, 8, …). Move to the next number that has not been crossed out — that number is prime. Cross out all of its multiples that haven't already been removed. Repeat this process until you have checked every prime up to

\sqrt{n}

. All remaining uncrossed numbers are prime.

Worked Example

Problem: Find all prime numbers up to 30 using the Sieve of Eratosthenes.

Step 1: List the integers from 2 to 30. Start with p = 2. Cross out all multiples of 2 (4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30).

Step 2: The next uncrossed number is 3. Cross out all multiples of 3 that remain (9, 15, 21, 27). Numbers like 6 and 12 were already removed.

Step 3: The next uncrossed number is 5. Cross out the remaining multiples of 5 (25). Since the next prime to check would be 7, and 7 > √30 ≈ 5.48, we can stop.

\sqrt{30} \approx 5.48

Answer: The primes up to 30 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Why It Matters

Identifying primes quickly matters in cryptography, where algorithms like RSA rely on the difficulty of factoring large numbers. The sieve also builds intuition for divisibility and multiples, which directly supports topics like modular arithmetic and greatest common factors.

Common Mistakes

Mistake: Starting to cross out multiples of a prime p beginning at 2p instead of p².

Correction: Every composite multiple of p that is less than p² will already have been crossed out by a smaller prime. You can safely start crossing out at p² to save time.