2011-08-05

Sieve of Eratosthenes


The Sieve of Eratosthenes is a reasonably efficient method for finding prime numbers.

Here is a quick implementation in Python (there are some further optimizations possible). For whatever reason, it made a lot more sense to me when I implemented it in Python than the previous implementation I’d seen done in Java.

# determine a list of all primes less than some number 'ceiling'
def list_primes(ceiling):

    # This array (list) will hold all the primes we find
    primes = []

    # a is a array (list) of true/false values (1 and 0)
    # indicating whether it's index is a prime number
    a = [1] * ceiling

    # we want to start with 2 as the first prime
    # so we mark out indexes 0 and 1 to start.
    a[0] = 0
    a[1] = 0

    # Now we begin the real algorithm.
    for i in range(0, len(a)):
        if a[i]:
            p = i
            n = 2
            while (n * p) < len(a):
                a[n * p] = 0
                n = n + 1

    # collect all the indicies that have been determined to be prime
    for i in range(0, len(a)):
        if a[i]:
            primes += [i]

    return primes

Wikipedia ( http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ) has a good writeup and visual of the method.

Basically I started with an array with slots for as many numbers as I am testing. The array starts with every slot marked true except for 0 and 1. Then for every number that you come to, if it is marked true (which happens first when you get to 2), you mark every multiple of the index as false.

So, as you interate through the numbers, if you come to a number and it is still marked true, then it is prime, so you mark all it’s multiples as false (not prime). And so on.

This ends up being faster than most of the schemes that I had tried that rely on testing numbers through division. In those cases you are still checking every number to see if it is divisable. But with this Sieve method all you have to do by the time you get to a number is check a truth value.

Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s