Finding Primes: Ancient Methods and Timeless Proofs

How do we find prime num­bers? And how do we know there isn't a largest one?

The Sieve of Er­atos­thenes

One of the ear­li­est known al­go­rithms for find­ing all prime num­bers up to a spec­i­fied in­te­ger was de­vised by the Greek math­e­mati­cian Er­atos­thenes of Cyrene (c. 276 BC – c. 194 BC). It's known as the Sieve of Er­atos­thenes.

The method is as fol­lows:

1. Create a list of con­sec­u­tive in­te­gers from 2 up to your de­sired limit, say $N$.

2. Start with the first prime number, $p=2$. Mark all mul­ti­ples of $p$ (i.e., $2p, 3p, 4p, \ldots$) up to $N$ as com­pos­ite.

3. Find the next number in the list that has not been marked. This number is the next prime. Let this be the new $p$.

4. Repeat step 2 with this new prime $p$.

5. Con­tin­ue this process until $p^2 > N$. All re­main­ing un­marked num­bers in the list are prime.

For ex­am­ple, to find primes up to 30:

• List: 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.

• $p=2$: Mark 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30. Re­main­ing: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29.

• Next un­marked is 3. $p=3$: Mark 9, 15, 21, 27 (6, 12, etc., al­ready marked). Re­main­ing: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29.

• Next un­marked is 5. $p=5$: Mark 25 (10, 15, etc., al­ready marked). Re­main­ing: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

• Next un­marked is 7. $p=7$. $7^2 = 49$, which is greater than 30. So we stop. The primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Euclid's Proof: The In­fini­tude of Primes

Are there in­fi­nite­ly many prime num­bers, or is there a largest prime? Euclid of Alexan­dria (c. 300 BC) pro­vid­ed an el­e­gant proof that there are indeed in­fi­nite­ly many primes. It's a clas­sic ex­am­ple of proof by con­tra­dic­tion.

Here's the essence of the proof:

1. Assume the op­po­site: Sup­pose there is a finite number of primes. Let them be $p_1, p_2, \ldots, p_n$, where $p_n$ is the largest prime.

2. Con­struct a new number: Con­sid­er the number $N$ formed by mul­ti­ply­ing all these primes to­geth­er and adding 1:

3. An­a­lyze $N$:
   • If $N$ itself is prime, then we have found a new prime number not in our orig­i­nal list $\{p_1, \ldots, p_n\}$, be­cause $N$ is clear­ly larger than any $p_i$. This con­tra­dicts our as­sump­tion that $p_n$ was the largest prime.
   • If $N$ is com­pos­ite, then it must be di­vis­i­ble by some prime number. Let this prime di­vi­sor be $q$.
     • Now, $q$ cannot be any of the primes in our list $\{p_1, \ldots, p_n\}$. Why? If $q$ were one of these $p_i$, then $q$ would divide $p_1 \cdot p_2 \cdot \ldots \cdot p_n$. Since $q$ also di­vides $N$, it must divide their dif­fer­ence: $N - (p_1 \cdot p_2 \cdot \ldots \cdot p_n)$.
     • But this dif­fer­ence is $( (p_1 \cdot p_2 \cdot \ldots \cdot p_n) + 1 ) - (p_1 \cdot p_2 \cdot \ldots \cdot p_n) = 1$.
     • So, $q$ must divide 1. The only pos­i­tive in­te­ger that di­vides 1 is 1 itself. But $q$ is a prime number, and by de­f­i­n­i­tion, primes are greater than 1. This is a con­tra­dic­tion.

4. Con­clu­sion: Our ini­tial as­sump­tion that there is a finite number of primes must be false. There­fore, there are in­fi­nite­ly many prime num­bers.

This proof is a cor­ner­stone of number theory, show­cas­ing the power of log­i­cal de­duc­tion.