Number System

Sieve of Eratosthenes

Students cross out selected cells in a large tabletop grid, leaving a few marked cells.

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.

In Spanish
criba de Eratóstenes
Topic
Prime numbers and number theory

Sieve of Eratosthenes in a picture

Sieve of Eratosthenes diagramAfter crossing out composite numbers through 20, the blue cells mark the primes.234567891011121314151617181920
After crossing out composite numbers through 20, the blue cells mark the primes.

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

Why can you stop crossing once the next prime exceeds √N?

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.