Sieve of Eratosthenes – finding prime numbers
MathematicsNumbers & ArithmeticAges 11–12
How do you mainly use this simulation?
Use it with your class: students open it from a link or a QR code, with no account needed.
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. The Divisibility screen tests any number for 2, 3, 4, 5, 6, 8, 9, 10 and 11 from its last digits, its digit sum or its alternating digit sum, shows why each test works from what the place values leave, and has missing-digit puzzles.
Lesson: Prime and composite numbers; factors and multiples; prime factorization; HCF and LCM; tests of divisibility
What it shows
The sieve of Eratosthenes finds every prime up to N: the smallest number not yet crossed out is prime and its multiples are crossed out; once p² > N, the rest are prime. Factor trees show that the prime factors are the same however a number is split. On HCF & LCM, shared primes go in the overlap of a Venn diagram. Divisibility shows why the quick tests work: 10, 100 and 1000 are each 1 more than a multiple of 9, so a number leaves the same remainder as its digit sum; for 11 the place values alternate +1 and −1.
How to use
On Sieve, press Next step or Auto and click cells to see factors and multiples; open Sieve settings to change N, the colors or the speed. On Factor trees, type n and split each orange number until every branch ends in a prime. On HCF & LCM, enter a and b and press Next step. On Divisibility, type a number, choose Divisible by and press Record; under Missing digits, choose a puzzle, set the digits and press Try these digits.
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, Divisibility
- Number to factorize n 2–1000
- First number a 2–500
- Second number b 2–500
- Word problem None, Two buses, Square tiles
- Activity (Divisibility screen) Test a number, Missing digits
- Number to test (Divisibility screen) 0–999999999999
- Divisor (Divisibility screen) 2, 3, 4, 5, 6, 8, 9, 10, 11
- Missing-digit puzzle (Divisibility screen) 31z5 ÷ 9, 48a23b ÷ 18, 3p7q8 ÷ 44, New puzzle
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?
- Why does the digit sum give the remainder on division by 9, but not on division by 7?