Sieve of Eratosthenes – finding prime numbers
MathematicsNumbers & ArithmeticAges 11–12
Use it with your class: students open it from a link or a QR code, with no account needed.
Next in Numbers & Arithmetic
A grid of numbers from 1 to N. Each time you click 'Next step', the smallest unmarked prime is highlighted in blue and its multiples are crossed out in a matching color. Click any cell to see its factors and multiples highlighted on the grid, and find out instantly whether that number is prime or composite. The Factor trees screen lets students split a number into a product of prime powers and see its factor pairs as rectangles; the HCF & LCM screen sorts the prime factors of two numbers into a Venn diagram, with bus-timetable and tiling problems.
Lesson: Prime and composite numbers; factors and multiples; prime factorization; HCF and LCM
What it shows
The sieve of Eratosthenes finds every prime up to N: from 2 on, the smallest number not yet crossed out is prime and its other multiples are crossed out; once p² > N, every remaining number is prime. The Factor trees screen shows the fundamental theorem of arithmetic: however a number is split, the prime leaves are the same, so its product of prime powers is unique, and the exponents give the number of factors. On HCF & LCM, shared primes go in the overlap of a Venn diagram: the overlap multiplies to the HCF, the whole diagram to the LCM, and HCF × LCM = a × b.
How to use
On Sieve, choose Sieve up to N, press Next step one prime at a time or use Auto, then click cells to check factors and multiples. On Factor trees, type n, tap an orange number and pick a factor pair until every branch ends in a prime; Split all shows the smallest-prime route. On HCF & LCM, enter a and b, press Next step to sort the primes into the Venn diagram, and choose a Problem such as buses or tiles.
Parameters you can change
- Sieve up to N 30–200
- Color multiples by the prime that crossed them out
- Run steps automatically
- Time per step (auto) 0.3–3 s
- Screen Sieve, Factor trees, HCF & LCM
- Number to factorize n 2–1000
- First number a 2–500
- Second number b 2–500
- Word problem None, Two buses, Square tiles
Questions to explore
- With N = 100, after which prime does the sieve stop crossing out new numbers? Why?
- Do two different factor trees for 360 always end with the same primes? Try three different first splits.
- Why is the LCM of two coprime numbers equal to their product?
