The sieve of Eratosthenes: finding primes by removing multiples

These teaching notes are for members

What the video covers, what to say before it, where a class usually goes wrong, and what to set afterwards. An account is free, and it opens every chapter of every book.

Create a free account Sign in

What to assume they know

Prime and composite: the rectangle test for a number's factors: prime and composite, classified by counting factors, and the status of 1
Common multiples: why the first "idli-vada" is 15: multiples, and continuing a run of them without listing
Reading a ten-by-ten grid by row and by column
Confidence that a composite number has a factor other than 1 and itself — the sieve's whole engine

What they should be able to do

Carry out the printed procedure on a hundred grid and produce the primes below 100
State what gets circled and what gets crossed out at each pass
Explain why the next uncrossed number must be prime
Explain why no composite number can survive to the end
Say why 1 is removed at the start and belongs to neither class
Read the finished grid for structure: gaps between neighbouring primes, pairs two apart, and the thinning-out as the numbers climb
Continue the method past 100 in principle, and say what would have to change
Name Eratosthenes and place him roughly in time, as the chapter does

Where it usually goes wrong

"You cross out 2 as well, since it is a multiple of 2." No — each number is circled first and only its later multiples go. Getting this wrong deletes every prime and is the single most common execution error.
"The sieve tests each number for primality." It tests nothing. It deletes multiples, and primality is the leftover. Students who think a test is happening cannot say why the method is faster than dividing.
"You have to run a pass for every number up to 100." You do not, and the reason is worth 30 seconds: once the pass for 7 is done, everything composite below 100 has already been struck, because a composite below 100 must have a prime factor of 7 or less.
"Crossed out means composite, so 1 is composite." The book removes 1 in the very first step for a different reason, and says explicitly that the crossed-out numbers other than 1 are the composites.
"The primes thin out, so they must eventually stop." They do thin out — question 3 on p.114 is about exactly that — and they do not stop. The chapter raises this and deliberately leaves it hanging.
"A gap of 1 between primes is impossible, since primes are odd." 2 and 3 are neighbours. It is the only such pair, and it is on the grid.

Questions to check understanding

Carry out the procedure on a grid of a stated range and list what survives
Say which numbers are struck on the pass for a stated prime
Explain why the next uncrossed number must be prime
Explain why a stated composite could not have survived
Give the smallest and largest gaps between neighbouring primes in a range
Find twin primes, or a run of consecutive composites, within a stated range
Say which pass is the last one that removes anything new, and why
The appendix bound with this chapter answers the §5.2 questions on footer pages 4 and 5

Examples worth working on the board

The procedure as printed (§5.2, p.113). Five numbered steps. Remove 1. Circle 2 and strike out its multiples beyond it. Find the next number still untouched, which is 3; circle it and strike out its multiples beyond it. Do the same for 5. Continue until every entry is either circled or struck. The book then states that the circles are the primes and the crosses, 1 aside, are the composites.
The printed grid (p.113). Checked against the printed page. A ten-by-ten table of 1 to 100 with the procedure already carried out: red diagonal strokes through the composites and 1, green rings around 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. This matters for the staging: the student's page shows the finished state, so the figure is showing them how their own picture came to be, not producing a new one. Redraw it; do not lift the artwork.
The margin objection (p.113). A speech bubble beside the grid insists this cannot be magic and that there has to be a reason it works. Checked against the printed page. It is the cue for sections 5 and 6, and it should be voiced as the student's own objection rather than paraphrased away.
Why the next survivor is prime. The argument to show: only circled numbers get a pass, so what has already run is a pass for every prime smaller than this one, and any of them that divided it would have struck it out. So no smaller prime divides it — and a number with any factor above 1 has a prime one — so its only factors are 1 and itself.
Why every composite falls. Take a composite's smallest factor other than 1. That one has to be prime, because a factor of it would be a smaller factor of the composite; so it was reached uncrossed, circled, and given a pass of its own, and on that pass the composite was struck as one of its multiples. The smallest matters: a composite's other factors may themselves be composite, and a composite never gets a pass.
Where the passes stop paying. By the time the pass for 11 begins, every multiple of 11 below 100 except 11 itself is already struck, because each of them carries a factor below 11. This is an added observation; the book does not raise it.
Reading the survivors (p.114, questions 1–3). Three questions on the finished grid: whether any even number besides 2 survives; the smallest and the largest gap between neighbouring primes below 100; and whether every row of ten holds the same number of primes, with which rows holding fewest and which most.
A run with no primes in it (p.114, question 7). Seven composites in a row, somewhere below 100. Give the range; finding the run is the exercise, and the finished grid makes it a matter of looking.
Twin primes (p.114, question 8). Defined in the question, with 3 and 5, and 17 and 19, as the printed examples. On the sieve grid they are the ringed cells with exactly one struck cell between them, which is a nice thing to see rather than compute.
The historical note (p.113). Eratosthenes, a Greek mathematician of about 2200 years ago, is credited with the method, and the book says the procedure carries on past 100. Checked against the printed page.
The open question (p.114 panel). The panel asks whether there is a largest prime or whether the list runs on for ever, credits Euclid with the answer, and defers it to a later class. Checked against the printed page.

Figures to have open

A ten-by-ten grid of 1 to 100 that can be shown moving cell by cell. This is the central figure and everything else hangs off it. Redraw: the printed grid on p.113 is the book's own artwork, and the redraw must end in the same state the student's page is in.
A one-axis layout of the primes below 100 with gaps dimensioned, for section 9. Standard schematic; the book does not print one.
No photograph or textbook data table is needed. No portrait of Eratosthenes is required or available — the book prints none, as the printed page of p.113 shows.

Where this sits in the book

NCERT Ganita Prakash, Class 6, Chapter 5 "Prime Time", §5.2 "Prime Numbers", pp.113–115 — the five printed steps and the worked grid (p.113), the historical attribution (p.113), the three grid-reading questions and the panel on the open problem (p.114), and the remaining questions (p.115)
Companion topic Prime and composite: the rectangle test for a number's factors for the definitions the sieve assumes
Solutions appendix bound with this chapter file, footer pages 4–5, for §5.2