Sieve of Eratosthenes

Section 10.2 Sieve of Eratosthenes

The Sieve of Eratosthenes is a method for finding all primes up to (and possibly including) a given natural \(n\text{.}\) This method works well when \(n\) is relatively small, allowing us to determine whether any natural number less than or equal to \(n\) is prime or composite.

We now explain how the Sieve of Eratosthenes can be used to find all prime numbers up to a given natural number. Recall that \(a\) is a multiple of \(b\) means that \(b\) divides \(a\text{,}\) see Definition 4.1.

Strategy 10.1. Sieve of Eratosthenes.

To find all prime numbers up to a given integer \(n\) we proceed as follows.

(a)

List all integers from \(2\) to \(n\)

(b)

The first integer on the list is \(2\text{,}\) and it is prime. Mark out all multiples of \(2\) that are bigger than \(2\) because they are composite.

We do not have to compute anything, as we can simply mark out every second number starting at \(2\text{.}\)

(c)

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\text{.}\)

(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\text{.}\)

(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\text{.}\)

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\text{.}\)

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