Sieve of Eratosthenes

Hannah, from Leicester High School for Girls, noticed that different patterns arose in her grid when she crossed out multiples of 2 and 3:

On the smaller grid all the multiples of 2 are in columns evenly spaced across the grid; this is because the grid is an even number of squares across. On the smaller grid, the multiples of three all go in diagonal lines. This is because the number of squares across in the grid is not a multiple of 3, it is a multiple of 10. This causes the numbers to shift one position to the left on each line, creating diagonal lines across the grid.

By analysing these patterns, she was able to predict what would happen when crossing out multiples of 4, 5 and 7. Hannah then correctly noticed that: 

The key to knowing whether numbers will be crossed out several times or not depends on factors.

This was extended by Sam from Oakworth Primary School, who correctly said:

The numbers that haven't been crossed out are all prime numbers. Prime numbers are numbers that can only be divided by 1 and themselves.

For the final challenge, Hannah gave some very good reasoning:

The way to find all the prime numbers between 1 and 400 is by crossing out all the multiples of prime numbers between 1 and 20.

This is because the square root of 400 is 20, so, say we'd found the multiples of all the prime numbers below 20, and then we started trying to find the 23 times tables:

it would be a waste of time because it would just be the reverse of the multiples we'd found so far - e.g. $23 \times 2$ is the same as $2 \times 23$, which we did earlier, so we'd just be going back on ourselves.

It is a good idea to use prime numbers, because all non-prime numbers can be made as a product of prime numbers - this is called prime factorisation.

Well done also to Krystof from Prague who recognised that he only needed to check prime numbers smaller than 20.

This problem has existed since Eratosthenes first devised the algorithm in the 3rd Century BC. The unique prime factorisation of numbers is essential to many areas of mathematics.