On this page
Eratosthenes was born in Cyrene, in present-day Libya, around 276 BCE and became the third librarian at Alexandria around 240 BCE, according to his MacTutor biography. He is famous for measuring the Earth with a shadow, but he is also credited with a way to find primes that coding students still meet: instead of testing each number for factors, cross out the multiples of the primes you already know. What survives is prime.
How does the sieve of Eratosthenes work?
The sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit by crossing out multiples of numbers, as the MoMath and Wolfram history of mathematics project describes it. The earliest known reference is in the Introduction to Arithmetic by Nicomachus of Gerasa (60-120 CE), who attributes it to Eratosthenes, according to the same source.
Write the numbers from 2 up to your limit (1 is neither prime nor composite).
Circle 2 and cross out every multiple of 2 after it.
Move to the next number not crossed out. It is prime: circle it and cross out its multiples.
Stop when the prime you reach, squared, is bigger than your limit.
Every number left uncrossed is prime.
Step 4 is the shortcut: only factors up to the square root of your limit need to be sieved out, the same page notes.
Worked example: what are the primes up to 50?
Start with 2 to 50.
Sieve with 2: cross out 4, 6, 8 and every even number up to 50.
Sieve with 3: start at 9, because 6 is already gone. New crossings: 9, 15, 21, 27, 33, 39, 45.
Sieve with 5: start at 25. New crossings: 25 and 35.
Sieve with 7: start at 49, the only new crossing.
Stop: the next survivor is 11, and 11 × 11 = 121 is bigger than 50.
What remains: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. That is 15 primes, and you never divided a single number. Each prime starts at its square because smaller multiples, such as 5 × 3, were crossed by an earlier prime.
How does the sieve connect to the fundamental theorem of arithmetic?
The first chapter of NCERT Class 10 maths, Real Numbers, states it as Theorem 1.1: "Every composite number can be expressed (factorised) as a product of primes, and this factorisation is unique, apart from the order in which the prime factors occur."
The sieve shows why the first half is true. Every composite gets crossed out, first by its smallest prime factor. Divide by that prime and look up the result on the same sieve:
84 was crossed first by 2, so 84 = 2 × 42.
42 was crossed first by 2, so 42 = 2 × 21.
21 was crossed first by 3, so 21 = 3 × 7.
7 survived, so it is prime. Stop.
So 84 = 2² × 3 × 7. That chain is a factor tree, the tool NCERT uses to break 32760 into 2³ × 3² × 5 × 7 × 13. Our guide to real numbers in Class 10 shows how factorisations become HCF, LCM and irrationality proofs. If your HCF and LCM answers keep going wrong at the factor tree, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
Is the sieve of Eratosthenes still used in programming?
Yes. In code, the sieve is an array of true or false values, one per number: start with everything true, then set the multiples of each prime to false, beginning at its square. The MacTutor biography adds that the sieve, in modified form, is still an important tool in number theory research.
There is a trap. In a 2009 paper in the Journal of Functional Programming, Melissa O'Neill showed that a widely used short functional program called "the Sieve of Eratosthenes" is not the sieve at all, and gave one that is (The Genuine Sieve of Eratosthenes). If your code divides each number to test it, you have written trial division. The real sieve only crosses out multiples.
A 20-minute sieve practice plan
Draw a 10-by-10 grid of 1 to 100 and sieve it with 2, 3, 5 and 7. Apart from 1, which is not prime, you should be left with 25 primes.
Look at the columns: why do multiples of 2 and 5 fall in straight lines?
Factorise 60, 91 and 98 with the "who crossed it first" rule.
Use two of those factorisations to find an HCF and LCM, as NCERT's Example 2 does for 6 and 20.
If divisibility rules feel shaky, revisit primes, co-primes and divisibility tests from Class 6, or look up the idea in the Fermi Concept Library, where each concept has its own lesson.
Sieve the grid by pencil, then in code. If both give the same primes, you have it.
