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 Definition4.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 Figure10.6 we apply the sieve of Eratosthenes to the natural numbers up to \(100\text{.}\)
Explore the sieving process in Figure10.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 Strategy10.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.
The Sieve of Eratosthenes can be used to produce tables of primes such as in Figure10.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\)
In Checkpoint10.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
Checkpoint10.9 illustrates that the number of prime numbers in sets of consecutive numbers of the same cardinality decreases as the numbers increase.
