| 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. |
