Math Fundamentals18 sections · 814 units
Open in Course

Sieve Example

(Finding primes up to 30)

Let us find all primes up to 30 using the sieve. Start with numbers 2 to 30.

1.1. Mark 2 as prime. Cross out 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 (all multiples of 2).

2.2. Next unmarked is 3. Mark 3 as prime. Cross out 9, 15, 21, 27 (multiples of 3 not already crossed).

3.3. Next unmarked is 5. Mark 5 as prime. Cross out 25 (only new multiple in range).

4.4. Next is 7. Since 7² = 49 > 30, we stop. All remaining unmarked numbers are prime: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.