Sieve of Eratosthenes

A natural number is prime if it has exactly two positive divisors, 1 and itself. Otherwise it is composite. The number 1 is usually regarded as being neither prime nor composite.
Eratosthenes of Cyrene (276-194 BC) was the first to estimate accurately the diameter of the earth. For several decades, he served as the director of the famous library in Alexandria. He was highly regarded in the ancient world, but unfortunately only fragments of his writing have survived. 
Eratosthenes devised a 'sieve' to identify prime numbers. A sieve is like a strainer that you drain spaghetti through when it is done cooking.  The water drains out, leaving your spaghetti behind. The Sieve of Eratosthenes drains out composite numbers and leaves prime numbers behind.
Make a list of all the integers less than or equal to n (and greater than one).
Strike out the multiples of all primes less than or equal to the square root of n.
Then the numbers that are left are the primes.
Note that if one divisor or factor of a number (other than a perfect square) is greater than its square root, then the other factor will be less than its square root. Hence all multiples of primes greater than the square root of  n  need not be considered. 

For example:  To find all the primes smaller than 50, first list the numbers from 2 to 50. 
 

2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
 
The first number 2 is prime, so keep it and delete its multiples.
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
 
The first number left is 3, so it is the first odd prime. Keep it and delete all of its multiples. Numbers like 6 and 12 are already deleted (as multiples of 2), but that need not concern us here.
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
 
The next number left is 5, the second odd prime. So keep it also and delete all of its multiples (25 and 35 are the only ones not yet deleted).
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
 
The next number left is 7, the third odd prime. So keep it also and delete all of its multiples (49 is the only one not yet deleted).
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
 
The next number left, 11, is larger than the square root of 50, so all of the numbers left are primes. Can you deduce why this is so?

The primes less than 50 are  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47  as indicated above. Notice we just found these primes without dividing. 

Proceed to the Sieve of Erathosthenes Applet by Albert Tremblay. Notice that it begins with a default table size of 50 as in our illustration.



Jill Britton Home Page
08-May-2005
Copyright Jill Britton