Sieve of Eratosthenes

The next integer on the list that is not marked out is 3, and it is prime. Mark out all multiples of 3 that are bigger than 3 because they are composite. (Note that some of these, such as 6, will already be marked out).

🔗

We do not have to compute anything, as we can simply mark out every third number starting at

3 .

🔗

(d)

🔗

The next integer on the list that is not marked out is 5, and it is prime. Mark out all multiples of 5 that are bigger than 5 because they are composite.

🔗

We do not have to compute anything, as we can simply mark out every fifth number starting at

5 .

🔗

(e)

🔗

Continue in this way until there is no next integer on the list that is not marked out.

🔗

The integers that are not marked out are all of the primes up to (and possibly including)

n .

🔗

The advantage of sieving is that any computing effort is replaced by counting.

🔗

In the video in Figure 10.6 we apply the sieve of Eratosthenes to the natural numbers up to

100 .

🔗

Figure 10.6. Sieve of Eratosthenes by Matt Farmer and Stephen Steward.

🔗

Explore the sieving process in Figure 10.7. Click on a number to have all its multiples marked by changing the field color to red and crossing them out. Numbers that you have clicked appear on green background. When there are no white fields left, the numbers in green fields are all the prime numbers up to 192.

🔗

It is most efficient to follow the strategy presented in Strategy 10.1. In particular that means first clicking on

2,

then clicking on the first number that remained white, which is

3

and so on. To illustrate the sieving better multiples are marked with a delay and different shades of red are used for multiples of different numbers.

🔗

Figure 10.7. Interactive Sieve of Eratosthenes up to

192 .

Click on a number to sieve out its multiples. Auto Sieve goes through the complete sieving process. Reset Sieve clears the sieve.

🔗

The Sieve of Eratosthenes can be used to produce tables of primes such as in Figure 10.8 without the need of factoring by simply counting.

🔗
$2,$ $3,$ $5,$ $7,$ $11,$ $13,$ $17,$ $19,$ $23,$ $29,$ $31,$ $37,$ $41,$ $43,$ $47,$ $53,$ $59,$ $61,$ $67,$ $71,$ $73,$ $79,$ $83,$ $89,$ $97,$ $101,$ $103,$ $107,$ $109,$ $113,$ $127,$ $131,$ $137,$ $139,$ $149,$ $151,$ $157,$ $163,$ $167,$ $173,$ $179,$ $181,$ $191,$ $193,$ $197,$ $199,$ $211,$ $223,$ $227,$ $229,$ $233,$ $239,$ $241,$ $251,$ $257,$ $263,$ $269,$ $271,$ $277,$ $281,$ $283,$ $293,$ $307,$ $311,$ $313,$ $317,$ $331,$ $337,$ $347,$ $349,$ $353,$ $359,$ $367,$ $373,$ $379,$ $383,$ $389,$ $397,$ $401,$ $409,$ $419,$ $421,$ $431,$ $433,$ $439,$ $443,$ $449,$ $457,$ $461,$ $463,$ $467,$ $479,$ $487,$ $491,$ $499,$ $503,$ $509,$ $521,$ $523,$ $541,$ $547,$ $557,$ $563,$ $569,$ $571,$ $577,$ $587,$ $593,$ $599,$ $601,$ $607,$ $613,$ $617,$ $619,$ $631,$ $641,$ $643,$ $647,$ $653,$ $659,$ $661,$ $673,$ $677,$ $683,$ $691,$ $701,$ $709,$ $719,$ $727,$ $733,$ $739,$ $743,$ $751,$ $757,$ $761,$ $769,$ $773,$ $787,$ $797,$ $809,$ $811,$ $821,$ $823,$ $827,$ $829,$ $839,$ $853,$ $857,$ $859,$ $863,$ $877,$ $881,$ $883,$ $887,$ $907,$ $911,$ $919,$ $929,$ $937,$ $941,$ $947,$ $953,$ $967,$ $971,$ $977,$ $983,$ $991,$ $997,$ $1009,$ $1013,$ $1019,$ $1021,$ $1031,$ $1033,$ $1039,$ $1049,$ $1051,$ $1061,$ $1063,$ $1069,$ $1087,$ $1091,$ $1093,$ $1097,$ $1103,$ $1109,$ $1117,$ $1123,$ $1129,$ $1151,$ $1153,$ $1163,$ $1171,$ $1181,$ $1187,$ $1193,$ $1201,$ $1213,$ $1217,$ $1223,$ $1229,$ $1231,$ $1237,$ $1249,$ $1259,$ $1277,$ $1279,$ $1283,$ $1289,$ $1291,$ $1297,$ $1301,$ $1303,$ $1307,$ $1319,$ $1321,$ $1327,$ $1361,$ $1367,$ $1373,$ $1381,$ $1399,$ $1409,$ $1423,$ $1427,$ $1429,$ $1433,$ $1439,$ $1447,$ $1451,$ $1453,$ $1459,$ $1471,$ $1481,$ $1483,$ $1487,$ $1489,$ $1493,$ $1499,$ $1511,$ $1523,$ $1531,$ $1543,$ $1549,$ $1553,$ $1559,$ $1567,$ $1571,$ $1579,$ $1583,$ $1597,$ $1601,$ $1607,$ $1609,$ $1613,$ $1619,$ $1621,$ $1627,$ $1637,$ $1657,$ $1759,$ $1777,$ $1783,$ $1787,$ $1789,$ $1801,$ $1811,$ $1823,$ $1831,$ $1847,$ $1861,$ $1867,$ $1871,$ $1873,$ $1877,$ $1879,$ $1889,$ $1901,$ $1907,$ $1913,$ $1931,$ $1933,$ $1949,$ $1951,$ $1973,$ $1979,$ $1987,$ $1993,$ $1997,$ $1999$

🔗

Figure 10.8. All prime numbers up to 2000

🔗

In Checkpoint 10.9 count the number of prime numbers between two given numbers.

Checkpoint 10.9. Count Primes.

The number of primes from 0 to 10 is

The number of primes from 10 to 20 is

The number of primes from 20 to 30 is

The number of primes from 30 to 40 is

The number of primes from 40 to 50 is

The number of primes from 50 to 60 is

The number of primes from 60 to 70 is

The number of primes from 70 to 80 is

The number of primes from 80 to 90 is

The number of primes from 90 to 100 is

🔗

Checkpoint 10.9 illustrates that the number of prime numbers in sets of consecutive numbers of the same cardinality decreases as the numbers increase.

Prev Top Next