picture of a number table

Prime Numbers: The Sieve of Eratosthenes

Each positive integer has at least two divisors, one and itself. A positive integer is a prime number if it is bigger than 1, and its only divisors are itself and 1. For example, 2, 3, 5, 7, 11, 13, 17, and 19 are prime numbers. Let’s try an ancient way to find the prime numbers between 1 and 100.

In addition to calculating the earth’s circumference and the distances from the earth to the moon and sun, the Greek polymath Eratosthenes (c. 276-c. 194 BCE) devised a method for finding prime numbers. Such numbers, divisible only by 1 and themselves, had intrigued mathematicians for centuries. By inventing his “sieve” to eliminate nonprimes—using a number grid and crossing off multiples of 2, 3, 5, and above—Eratosthenes made prime numbers considerably more accessible.

Each prime number has exactly 2 factors: 1 and the number itself. The Greeks understood the importance of primes as the building blocks of all positive integers. In his Elements, Euclid (about 300 BCE) stated many properties of both composite numbers (integers above one that can be made by multiplying other integers) and primes. These included the fact that every integer can be written as a product of prime numbers, or it is itself prime. A few decades later Eratosthenes developed his method, which can be extended to uncover primes.

Get your number grid (Click here for a copy that you may print out) and your pencil out! We will use Eratosthenes’ sieve to discover the prime numbers between 1 and 100. Using the grid, it is clear that 1 is not a prime number, since its only factor is 1. The first prime number—and the only even prime number—is 2. Since all other even numbers are divisible by 2, they cannot be primes, so all other prime numbers must be odd. So take your pencil and mark out all multiples of 2: 4, 6, …., 98, 100. That takes out 49 of the numbers!

picture of a number table

The next prime, 3, has only 2 factors, so all the other factors of 3 cannot be primes. So use your pencil to cross out 6 (it’s already gone), 9, 12(already gone), 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99.

picture of a number table

We continue this process, crossing out multiplies of 5 (I found 25, 35, 65, 85, 95), multiples of 7 (49, 77, 91), 11 (none), 13 (none).(In general we need to test divisors only up to the square root of the number.) And finally we have:

picture of a number table

The prime numbers up to 100: 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.

Oh, no! This list contains 26 numbers, and there are only 25 prime numbers less than 100. Which number in the list is actually composite?? 91 = 7*13!

Notice that we don’t have to go above multiples of nine to get the non-prime (i.e. composite) numbers!

There are 25 prime numbers between 1 and 100.

There are 21 prime numbers between 101 to 200.

There are 16 prime numbers between 201 and 300.

Prime numbers become less common as numbers get larger.

Even Euclid knew that there are infinitely many primes! (The proof is easy!)

FYI, Euclid proved the “fundamental theorem of arithmetic”, that every integer greater than one can be expressed as a product of primes in only one way. (So once you factor a number, it is unique. You will never factor it with different prime numbers.)

There is a theorem that is designed to calculate approximately how many primes there are that are less than or equal to any number x.

A few other very cool things about prime numbers

“Twin primes” are primes that are exactly two apart. Some twin primes are 3 and 5, 5 and 7, 11 and 13, 17 and 19, 29 and 31, …. (Can you find all the twin primes up to 200?)

There is only one set called “Triplet primes”: 3, 5, 7.

It is NOT KNOWN if there are infinitely many twin primes!

The largest known prime number (as of January 2020) is 282,589,933 − 1, a number which has 24,862,048 digits when written in base 10. It was found by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018. Here it is:

148894445742041325547806458472397916603026273992795324185271289425213239361064475310309971132180337174752834401423587560 ...

(24,861,808 digits omitted)



Goldbach’s conjecture.

In 1742, Russian mathematician Christian Goldbach wrote to Leonard Euler, the leading mathematician of the time. Goldbach believed he had observed something remarkable—that every even integer bigger than 2 can be split into two prime numbers, such as 6 = 3 + 3 or 8 = 3 + 5. Euler was convinced he was right, but he could not prove it.

Manual and electronic methods have as yet failed to find any even number that does not conform to the conjecture. In 2013, a computer tested every even number up to 4*1018 without finding one. The bigger the number, the more pairs of primes can create it, so it seems highly likely that the conjecture is valid and no exception will be found. But mathematicians require a definitive proof.

Can you show that Goldbach’s conjecture holds for all even numbers from 4 through 100?

Webpage by Breanna Widner
Lesson Index