Sieve of Eratosthenes definition
The sieve of Eratosthenes finds primes by crossing out multiples of each prime up to the square root of the chosen limit.
Sieve of Eratosthenes in a picture
How it works
List the integers from 2 through N. Keep the smallest uncrossed number as prime and cross out its multiples starting at its square. Repeat while the prime’s square is at most N. Every composite has a prime factor at most its square root.
Worked examples
When processing 3, which multiple is the first you need to cross out?
9, because 6 has already been crossed out as a multiple of 2.
Which primes do you use to cross out multiples through 30?
2, 3, and 5. The next prime is 7 and 7² is greater than 30.
Why do you leave 2 uncrossed?
2 is prime. Its proper multiples 4, 6, 8, and so on are composite.
Common mistake
Start each new prime’s crossing at its square. The smaller composite multiples were already marked by smaller primes.
Quick check
Which is the first multiple of 5 you need to cross out when you process 5?
Show answer
25.
What does an uncrossed number at the end represent?
Show answer
A prime number.
Sources
Flashcard
Sieve of Eratosthenes
Reveal the definition
The sieve of Eratosthenes finds primes by crossing out multiples of each prime up to the square root of the chosen limit.
Effortless Math. “Sieve of Eratosthenes.” Math Dictionary.
