Prime Sieves

One way to find every prime number up to some ceiling \(N\in\mathbb{N}\) is to test the numbers \(2, 3, \ldots, N\) one at a time. A sieve takes the opposite approach: eliminate every composite number between \(2\) and \(N\), and whatever is left over must be prime.

The Sieve of Eratosthenes

The following strategy is named for the Greek mathematician Eratosthenes. It is one of the oldest algorithms still in common use.

Starting with the candidate set \(C = \{2, 3, \ldots, N\}\):

  1. The smallest candidate \(p\in C\) is prime.

  2. Remove the multiples \(p^2, p^2 + p, p^2 + 2p, \ldots\) up to \(N\) from \(C\). Each smaller multiple \(kp\) with \(2 \le k < p\) has a prime factor smaller than \(p\), so it has already been removed from \(C\).

  3. Repeat steps 1 and 2 until \(p^2 > N\).

Every number left at the end is prime. The following shows how this strategy proceeds for \(N = 100\).

Start with the numbers \(1\) through \(100\). The number \(1\) is not prime, so cross it out.

\[\begin{split} \begin{array}{cccccccccc} {\color{red}\cancel{1}} & 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 \\ 51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 \\ 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70 \\ 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 \\ 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 & 90 \\ 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 \end{array} \end{split}\]

The smallest remaining number, \(2\), is prime. Cross out its multiples starting at \(2^2 = 4\).

\[\begin{split} \begin{array}{cccccccccc} \cancel{1} & {\color{red}\boxed{2}} & 3 & {\color{red}\cancel{4}} & 5 & {\color{red}\cancel{6}} & 7 & {\color{red}\cancel{8}} & 9 & {\color{red}\cancel{10}} \\ 11 & {\color{red}\cancel{12}} & 13 & {\color{red}\cancel{14}} & 15 & {\color{red}\cancel{16}} & 17 & {\color{red}\cancel{18}} & 19 & {\color{red}\cancel{20}} \\ 21 & {\color{red}\cancel{22}} & 23 & {\color{red}\cancel{24}} & 25 & {\color{red}\cancel{26}} & 27 & {\color{red}\cancel{28}} & 29 & {\color{red}\cancel{30}} \\ 31 & {\color{red}\cancel{32}} & 33 & {\color{red}\cancel{34}} & 35 & {\color{red}\cancel{36}} & 37 & {\color{red}\cancel{38}} & 39 & {\color{red}\cancel{40}} \\ 41 & {\color{red}\cancel{42}} & 43 & {\color{red}\cancel{44}} & 45 & {\color{red}\cancel{46}} & 47 & {\color{red}\cancel{48}} & 49 & {\color{red}\cancel{50}} \\ 51 & {\color{red}\cancel{52}} & 53 & {\color{red}\cancel{54}} & 55 & {\color{red}\cancel{56}} & 57 & {\color{red}\cancel{58}} & 59 & {\color{red}\cancel{60}} \\ 61 & {\color{red}\cancel{62}} & 63 & {\color{red}\cancel{64}} & 65 & {\color{red}\cancel{66}} & 67 & {\color{red}\cancel{68}} & 69 & {\color{red}\cancel{70}} \\ 71 & {\color{red}\cancel{72}} & 73 & {\color{red}\cancel{74}} & 75 & {\color{red}\cancel{76}} & 77 & {\color{red}\cancel{78}} & 79 & {\color{red}\cancel{80}} \\ 81 & {\color{red}\cancel{82}} & 83 & {\color{red}\cancel{84}} & 85 & {\color{red}\cancel{86}} & 87 & {\color{red}\cancel{88}} & 89 & {\color{red}\cancel{90}} \\ 91 & {\color{red}\cancel{92}} & 93 & {\color{red}\cancel{94}} & 95 & {\color{red}\cancel{96}} & 97 & {\color{red}\cancel{98}} & 99 & {\color{red}\cancel{100}} \end{array} \end{split}\]

The next remaining number, \(3\), is prime. Cross out its multiples starting at \(3^2 = 9\).

\[\begin{split} \begin{array}{cccccccccc} \cancel{1} & \boxed{2} & {\color{red}\boxed{3}} & \cancel{4} & 5 & \cancel{6} & 7 & \cancel{8} & {\color{red}\cancel{9}} & \cancel{10} \\ 11 & \cancel{12} & 13 & \cancel{14} & {\color{red}\cancel{15}} & \cancel{16} & 17 & \cancel{18} & 19 & \cancel{20} \\ {\color{red}\cancel{21}} & \cancel{22} & 23 & \cancel{24} & 25 & \cancel{26} & {\color{red}\cancel{27}} & \cancel{28} & 29 & \cancel{30} \\ 31 & \cancel{32} & {\color{red}\cancel{33}} & \cancel{34} & 35 & \cancel{36} & 37 & \cancel{38} & {\color{red}\cancel{39}} & \cancel{40} \\ 41 & \cancel{42} & 43 & \cancel{44} & {\color{red}\cancel{45}} & \cancel{46} & 47 & \cancel{48} & 49 & \cancel{50} \\ {\color{red}\cancel{51}} & \cancel{52} & 53 & \cancel{54} & 55 & \cancel{56} & {\color{red}\cancel{57}} & \cancel{58} & 59 & \cancel{60} \\ 61 & \cancel{62} & {\color{red}\cancel{63}} & \cancel{64} & 65 & \cancel{66} & 67 & \cancel{68} & {\color{red}\cancel{69}} & \cancel{70} \\ 71 & \cancel{72} & 73 & \cancel{74} & {\color{red}\cancel{75}} & \cancel{76} & 77 & \cancel{78} & 79 & \cancel{80} \\ {\color{red}\cancel{81}} & \cancel{82} & 83 & \cancel{84} & 85 & \cancel{86} & {\color{red}\cancel{87}} & \cancel{88} & 89 & \cancel{90} \\ 91 & \cancel{92} & {\color{red}\cancel{93}} & \cancel{94} & 95 & \cancel{96} & 97 & \cancel{98} & {\color{red}\cancel{99}} & \cancel{100} \end{array} \end{split}\]

The next remaining number, \(5\), is prime. Cross out its multiples starting at \(5^2 = 25\).

\[\begin{split} \begin{array}{cccccccccc} \cancel{1} & \boxed{2} & \boxed{3} & \cancel{4} & {\color{red}\boxed{5}} & \cancel{6} & 7 & \cancel{8} & \cancel{9} & \cancel{10} \\ 11 & \cancel{12} & 13 & \cancel{14} & \cancel{15} & \cancel{16} & 17 & \cancel{18} & 19 & \cancel{20} \\ \cancel{21} & \cancel{22} & 23 & \cancel{24} & {\color{red}\cancel{25}} & \cancel{26} & \cancel{27} & \cancel{28} & 29 & \cancel{30} \\ 31 & \cancel{32} & \cancel{33} & \cancel{34} & {\color{red}\cancel{35}} & \cancel{36} & 37 & \cancel{38} & \cancel{39} & \cancel{40} \\ 41 & \cancel{42} & 43 & \cancel{44} & \cancel{45} & \cancel{46} & 47 & \cancel{48} & 49 & \cancel{50} \\ \cancel{51} & \cancel{52} & 53 & \cancel{54} & {\color{red}\cancel{55}} & \cancel{56} & \cancel{57} & \cancel{58} & 59 & \cancel{60} \\ 61 & \cancel{62} & \cancel{63} & \cancel{64} & {\color{red}\cancel{65}} & \cancel{66} & 67 & \cancel{68} & \cancel{69} & \cancel{70} \\ 71 & \cancel{72} & 73 & \cancel{74} & \cancel{75} & \cancel{76} & 77 & \cancel{78} & 79 & \cancel{80} \\ \cancel{81} & \cancel{82} & 83 & \cancel{84} & {\color{red}\cancel{85}} & \cancel{86} & \cancel{87} & \cancel{88} & 89 & \cancel{90} \\ 91 & \cancel{92} & \cancel{93} & \cancel{94} & {\color{red}\cancel{95}} & \cancel{96} & 97 & \cancel{98} & \cancel{99} & \cancel{100} \end{array} \end{split}\]

The next remaining number, \(7\), is prime. Cross out its multiples starting at \(7^2 = 49\).

\[\begin{split} \begin{array}{cccccccccc} \cancel{1} & \boxed{2} & \boxed{3} & \cancel{4} & \boxed{5} & \cancel{6} & {\color{red}\boxed{7}} & \cancel{8} & \cancel{9} & \cancel{10} \\ 11 & \cancel{12} & 13 & \cancel{14} & \cancel{15} & \cancel{16} & 17 & \cancel{18} & 19 & \cancel{20} \\ \cancel{21} & \cancel{22} & 23 & \cancel{24} & \cancel{25} & \cancel{26} & \cancel{27} & \cancel{28} & 29 & \cancel{30} \\ 31 & \cancel{32} & \cancel{33} & \cancel{34} & \cancel{35} & \cancel{36} & 37 & \cancel{38} & \cancel{39} & \cancel{40} \\ 41 & \cancel{42} & 43 & \cancel{44} & \cancel{45} & \cancel{46} & 47 & \cancel{48} & {\color{red}\cancel{49}} & \cancel{50} \\ \cancel{51} & \cancel{52} & 53 & \cancel{54} & \cancel{55} & \cancel{56} & \cancel{57} & \cancel{58} & 59 & \cancel{60} \\ 61 & \cancel{62} & \cancel{63} & \cancel{64} & \cancel{65} & \cancel{66} & 67 & \cancel{68} & \cancel{69} & \cancel{70} \\ 71 & \cancel{72} & 73 & \cancel{74} & \cancel{75} & \cancel{76} & {\color{red}\cancel{77}} & \cancel{78} & 79 & \cancel{80} \\ \cancel{81} & \cancel{82} & 83 & \cancel{84} & \cancel{85} & \cancel{86} & \cancel{87} & \cancel{88} & 89 & \cancel{90} \\ {\color{red}\cancel{91}} & \cancel{92} & \cancel{93} & \cancel{94} & \cancel{95} & \cancel{96} & 97 & \cancel{98} & \cancel{99} & \cancel{100} \end{array} \end{split}\]

The next remaining number is \(11\), but \(11^2 = 121 > 100\), so the sieve stops. Every number left is prime.

\[\begin{split} \begin{array}{cccccccccc} \cancel{1} & \boxed{2} & \boxed{3} & \cancel{4} & \boxed{5} & \cancel{6} & \boxed{7} & \cancel{8} & \cancel{9} & \cancel{10} \\ {\color{red}\boxed{11}} & \cancel{12} & {\color{red}\boxed{13}} & \cancel{14} & \cancel{15} & \cancel{16} & {\color{red}\boxed{17}} & \cancel{18} & {\color{red}\boxed{19}} & \cancel{20} \\ \cancel{21} & \cancel{22} & {\color{red}\boxed{23}} & \cancel{24} & \cancel{25} & \cancel{26} & \cancel{27} & \cancel{28} & {\color{red}\boxed{29}} & \cancel{30} \\ {\color{red}\boxed{31}} & \cancel{32} & \cancel{33} & \cancel{34} & \cancel{35} & \cancel{36} & {\color{red}\boxed{37}} & \cancel{38} & \cancel{39} & \cancel{40} \\ {\color{red}\boxed{41}} & \cancel{42} & {\color{red}\boxed{43}} & \cancel{44} & \cancel{45} & \cancel{46} & {\color{red}\boxed{47}} & \cancel{48} & \cancel{49} & \cancel{50} \\ \cancel{51} & \cancel{52} & {\color{red}\boxed{53}} & \cancel{54} & \cancel{55} & \cancel{56} & \cancel{57} & \cancel{58} & {\color{red}\boxed{59}} & \cancel{60} \\ {\color{red}\boxed{61}} & \cancel{62} & \cancel{63} & \cancel{64} & \cancel{65} & \cancel{66} & {\color{red}\boxed{67}} & \cancel{68} & \cancel{69} & \cancel{70} \\ {\color{red}\boxed{71}} & \cancel{72} & {\color{red}\boxed{73}} & \cancel{74} & \cancel{75} & \cancel{76} & \cancel{77} & \cancel{78} & {\color{red}\boxed{79}} & \cancel{80} \\ \cancel{81} & \cancel{82} & {\color{red}\boxed{83}} & \cancel{84} & \cancel{85} & \cancel{86} & \cancel{87} & \cancel{88} & {\color{red}\boxed{89}} & \cancel{90} \\ \cancel{91} & \cancel{92} & \cancel{93} & \cancel{94} & \cancel{95} & \cancel{96} & {\color{red}\boxed{97}} & \cancel{98} & \cancel{99} & \cancel{100} \end{array} \end{split}\]

Problem 4

Write a function named prime_sieve() that accepts a positive integer \(N\). Use the sieve of Eratosthenes to find every prime less than or equal to \(N\):

  1. Initialize a set of candidates \(C = \{2, 3, \ldots, N\}\).

  2. For \(p = 2, 3, 4, \ldots\), if \(p\in C\), remove its multiples \(p^2, p^2 + p, p^2 + 2p, \ldots\) from \(C\).

  3. Stop when \(p^2 > N\); the remaining candidates are all prime.

Return the list of resulting primes, sorted from least to greatest.

Hint 1: Store the candidates in a set, and remove numbers with the discard() method.
Hint 2: Convert the candidate set to a sorted list at the end with sorted().

Test Cases

print(prime_sieve(1))
print(prime_sieve(2))
print(prime_sieve(4))
print(prime_sieve(100))
[]
[2]
[2, 3]
[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]

Other Prime Sieves

The sieve of Eratosthenes is not the only prime sieve. The sieve of Sundaram finds the odd primes by crossing out numbers of the form \(i + j + 2ij\), and the sieve of Atkin is asymptotically faster for very large bounds.