Unit 2 · Topic 02 · Number Play
Kabir tried to list every prime number from 1 to 100 by testing each one for factors, one at a time.
Forty minutes in, he had checked eleven numbers and made three mistakes already.
Ms. Rao handed him a grid and a pencil and said, "Cross out numbers instead of testing them. You'll be done in five minutes."
Kabir had a grid of numbers 1 to 100 and a plan: check each number one by one, trying to divide it by everything smaller, to see if it was prime. By the time he reached 23, he had already wrongly called 21 a prime number, forgetting it divides by 7. Ms. Rao stopped him. "Testing each number alone is slow and easy to mess up. Try crossing numbers out instead of testing them in."
She had him cross out 1 first — not prime, not composite, a special case. Then she said, "Circle 2, and cross out every multiple of 2 after it: 4, 6, 8, 10, and so on." Kabir did, crossing out half the grid in seconds. "Now circle the next number that isn't crossed out — that's 3 — and cross out every multiple of 3 you haven't already crossed: 9, 15, 21, 27..." 21 got crossed out this time, automatically, no testing needed.
They repeated it for 5, then 7. By the time they reached 7, most of the grid was already crossed out from earlier rounds, so there was very little left to check. Every number still uncircled and uncrossed once they passed 7 (since the next number, 11, times itself already exceeds 100) turned out to be prime automatically, with no individual testing at all.
Kabir counted the circled numbers: 25 primes between 1 and 100. "I didn't test a single one of them directly," he said, surprised. "I just crossed out everything that WASN'T prime, methodically, and whatever survived had to be prime." Ms. Rao nodded. "That's the Sieve of Eratosthenes — named for the Greek mathematician who invented it over two thousand years ago. Sift out the composites, and the primes are just what's left."
A prime number has exactly two factors: 1 and itself, like 2, 3, 5, 7, 11. A composite number has more than two factors, like 4, 6, 8, 9. The number 1 is neither prime nor composite — it only has one factor, itself.
The Sieve of Eratosthenes finds all primes up to a limit by crossing out multiples instead of testing each number individually: circle the smallest uncrossed number, cross out every multiple of it, then repeat with the next uncrossed number.
This method is fast because crossing out a multiple of 2, 3, 5, or 7 automatically rules out many composite numbers at once, without ever having to check their factors directly — whatever survives every round of crossing-out must be prime.
Draw a grid of numbers 1 to 50 on paper. Cross out 1, circle 2, cross its multiples, then circle 3, cross its multiples, and continue until every number is either circled or crossed. Count the primes you found.
Pick any number your sieve marked composite and write out two different factor pairs for it, showing it really does have more than two factors.
Loading questions…