Sieve of Eratosthenes (Part 2)

Eratosthenes

    Eratosthenes was by all accounts a polymath and probably the first recorded one in history. He was a close friend of Archimedes (of the Eureka fame) who also shared his love of Mathematics. Eratosthenes list of achievements is truly impressive. He was a mathematician, geographer, poet, astronomer, music theorist, the inventor of geography and the chief librarian at the ancient Library of Alexandria. While Eratosthenes worked at the library, a more modern theoretical physicist named Albert Einstein worked at the patent office. This allowed them to be exposed to many different ideas from various perspectives. This I believe is one of the critical reasons as to why both Einstein and Eratosthenes were so far ahead of their times.

    I am just going to focus on one of his achievements, which is a sieve used to find consecutive prime numbers that was named after him. Eratosthenes was a Greek citizen born in 276 BC in Shahhat, Libya and eventually died in 194 BC in his much beloved Alexandria, Egypt. After loosing his vision he suffered a bout of depression, leading him to voluntarily starve himself to death at the age of 82.  The reason it is important to keep these dates in perspective is because the next sieve to find primes was invented in 1934 by S. P. Sundaram, an Indian student 2128 years later. The one after that was invented in 2004 by Arthur Oliver Lonsdale Atkin a British mathematician 70 years later. Given the time that Eratosthenes lived in and the resources available to him, you can appreciate the sheer magnitude of his discovery. Although now there are so many faster ways to find large primes like "Fermat little theorem" or the "Sieve of Atken", Eratosthenes's sieve was used well into the 21st century, for cryptography and other purposes. 

    My simple python script to find primes turned into a history lesson which I thought is important to share. Learning is the act of acquiring by synthesizing different types of information. Not only were Einstein and Eratosthenes exposed to different ideas,  they wanted to learn by exploring the unknown. Today with the democratization of technology, and the penetration of the internet almost all information is a google search away. You are only bound by your willingness to learn. Keep your eyes open, find what you love to do and explore away. 

Sieve of Eratosthenes (Part 1)

    In an attempt to grasp the fundamentals of python, I decided to give myself a challenge. The challenge was to find prime numbers between 1 and x. The idea here was that while attempting to find these primes, I would end up learning about loops, conditional statements, breaks, e.t.c. I finished the challenge, but ended up learning a lot more than just the fundamentals of python.

    I started off with the brute force method. This method looped through a set of numbers one at a time, and then made sure that only 1 mod the current number and the current number mod itself had a remainder of 0. If so it was a prime number. Imagine looping though a set of numbers 1 to x, where x was greater than or equal to 1,000,000. You will quickly realise that although this method worked it had obvious flaws. It was inefficient and time consuming. To speed up the process I started storing the primes in memory as I kept finding them. Then I started looping through the found primes and doing a modulus with the current number. This reduced the number of modulo operations I had to do, but it was still fairly time consuming.

    I needed to find yet a faster method to find primes and came across a simple but elegant method called the "Sieve of Eratosthenes". Eratosthenes used a process of elimination until you were only left with primes. His method is summed up below. 

1. Create a list of consecutive numbers from 1 to x and cross out 1 because it is not a prime number.
2. Start with the next number p which is 2 in this case and circle it. Next eliminate all multiples of p (eg:- 4,6,8,e.t.c.)
3. p takes on the value of the next number in the list and repeat step 2
4. Keep going until p multiplied by p is greater than or equal to x

Sieve of Eratosthenes

    This was much quicker and could be implemented writing a lot less code. This got me interested in Eratosthenes and I wanted to know more about him. (Continued in Part 2 .... )