Prime Numbers & The Sieve of Eratosthenes
When it comes to number envy, primes definitely steal the show, and for good reason. They’re fundamental, mysterious and hard to come by. They’re valuable for encryption and at the heart of some of the most elusive problems of history, the Riemann Hypothesis & Goldbach’s Conjecture.
So let’s get to know these numbers a little.
Definitions
- A number is prime if it has exactly two positive whole number divisors, one and itself.
- A number is composite if it has more than two positive whole number divisors.
That means there exists numbers that are neither prime nor composite such as 0, 1 and any non-whole numbers.
Prime numbers are fascinating because there is no pattern or formula to predict them. The larger they get, the more difficult they are to find because the list of possible numbers they cannot be divided by grows. Needless to say, really large prime numbers are few and far between.
Currently, the largest known prime number was found in 2013 and is 17,425,170 digits long! The number is so big that it is recorded as:
Mathematicians call primes that are one less than a power of 2 (like the one above) Mersenne Primes, named after 17th century French mathematician, music theorist, and Minim Friar Marin Mersenne.
Discovering a new prime number is a noteworthy accomplishment and could even win you a small fortune. The Electronic Frontier Association promises to award $150k to the first person or group who discovers a prime number at least 100,000,000 digits long and $250k to the first person or group who discovers a prime number at least 1,000,000,000 digits.
How do we know primes this big even exist?
In the next lesson, I’ll show you how we know that there exists an infinite quantity of prime numbers. So stay tuned!
But first…
Let’s find the first 25 prime numbers. To do this we’ll use a technique pioneered by ancient Greek mathematician Eratosthenes.
(Note: If you have children, this is a great introductory exercise. See if you can help them figure out how to eliminate numbers to find the primes.)
The Sieve of Eratosthenes
To discover the first 25 prime numbers, we’ll sift out all the composite numbers between 1 and 100 using multiples.
Begin by listing out the numbers from 1 to 100.
Now erase all of the multiples of 2, except 2 itself.
Next erase all multiples of 3, 5 and 7, except for 3, 5 and 7 themselves.
There are no multiples of 11, 13, 17, 19, … left on the list. Finally remove 1 since it isn’t prime. What’s left is the first 25 prime numbers.
Thanks for reading!
❤ STAY CONNECTED ❤
Stay up-to-date with everything Math Hacks is up to!
