The Sieve of Eratosthenes
Solve problems by finding the prime factors of numbers.
Number Framework Stage 8
Eratosthenes, who lived in Greece from about 276 to 195 BC, invented a system to find prime numbers. It consists of crossing out every second number except 2 on a grid then every third number except 3, and so on. The numbers not crossed out are prime. (A discussion about 1 being a special number in that it is neither prime nor non-prime may be worthwhile.)
Give each student a copy of the grid. Notice the number 1 is shaded to indicate it is special. 2 is prime and ringed. Discuss how to cross out all the multiples of 2. (Answer: For example cross out whole columns at a time.)
Ring 3 and cross out all multiples of 3 (that is 6, 9, 12 ... ). Ring 5 and cross out multiples of 5. Continue until all the prime numbers ≤ 200 are ringed.
Discussion: Why is this called a sieve?
Understanding Number Properties:
Describe how you would determine whether 349 is prime using the Sieve of Eratosthenes. Don’t actually do it. Is the method generally useful? Consider for example, testing whether 179 781 is prime.