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 .... )