Paul Mouzas

There is a git repository on Github that contains 100 ideas for programming projects. Most of them aren't too difficult. I will occasionally do one or two projects to keep my programming skills sharp, and maybe learn a thing or two.

Today, I decided to implement the Sieve of Erathosthenes from the list of projects. I followed these instructions from Wikipedia:

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked).
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

Using these instructions as a guide, I translated everything to Python. I used a dictionary to keep track of the primes. Any key that had a value of False, is not a prime:

def sieve(n):
    d = dict.fromkeys(range(2,n+1), True)
    for i in range(2,n+1):
        if d[i]:
            for j in range(i*2, n+1, i):
                d[j] = False
    return [x for x in d if d[x]]