The Sieve of Eratosthenes is a simple way to make a list of prime numbers. The basic idea is to make an array of numbers. Starting with 2, cross out all multiples of 2 greater than 2. Next cross out all of the multiples of 3 greater than 3.
More generally, find the next number on the list that is not yet crossed out (in this example, 5 would be next) and cross out its multiples after the first one.
Continue until the next prime number p is such that p ^ 2 > the largest number in the list. For example, if you are making a list of prime numbers between 0 and 100, you would cross out multiples of 7 and then stop because the next number not crossed out would be 11 and 11 ^ 2 = 121, which is greater than 100.
Euler noticed an improvement. When you are considering the multiples of the next prime p, you only need to consider numbers that are p * q where q >= p and q ia prime.
For example, when you consider multiples of 7 you would cross out 7 * 7, 7 * 11, 7 * 13, etc. All of the other multiples have already been crossed out.
Any numbers q smaller than 7 were considered when those numbers were considered. For example, 7 * 5 was considered when you crossed out multiples of 5.
Non-prime numbers q bigger than 7 were considered when the factors of those numbers were considered. For example, you crossed out 7 * 21 when you examined multiples of 3.
Enter a value for the largest number to check and click Go. The following code shows how the program works.