Pythonism

code and the oracular

More about primes…The Sieve of Eratosthenes

with 3 comments

The Sieve of Eratosthenes is the most commonly known way to generate lists of primes. Those Greeks knew what they were doing ! It is a nice simple algorithm for beginning programmers. Start with all the natural numbers up to n, and then cross out all the composites starting with even numbers (greater than 2), then multiples of 3 and so on. once you have got up to crossing out multiples of the square root of n anything left must be prime.

As usual Python is straightforward:

def sieve(x):
    a=range(2,x+1)
    for b in range(2,int(x**0.5)+1):
        for z in a:
            if z%b==0 and z!=b:
                a.remove(z)
    return a
print sieve(10000)

There is some redundancy in this code because having started eliminating mutliples of two it then tries to eliminate multiples of 4 (of which there can’t be any since any multiple of 2 is also of 4 and will have been eliminated) and so on through 6,8,9 etc. Coding to avoid this seems to result in a slower and more cumbersome program so I kept it simple.

Notice that this is a generator, useful for finding more than one prime. It’s possibly the simplest to code but you should also look at exploring primes since the function there is faster as I timed it. For really large numbers even these tests can take much too long to be feasible, and that’s why specialists like cryptographers often rely on probabilistic tests that declare a number to be, say, 99.999% likely to be prime, although not 100% certain.

Another algorithm for generating all the primes up to a given number is called the “Sieve of Atkin”.

http://en.wikipedia.org/wiki/Sieve_of_Atkin

it is slightly more complex and we’ll leave it for later.

Advertisements

Written by Luke Dunn

May 28, 2008 at 7:29 pm

Posted in Math, Primes

Tagged with , , ,

3 Responses

Subscribe to comments with RSS.

  1. I just learned about this sieve the other day from an old math book (never having heard of it before). My daughter and I sat and calculated doing the sieve my hand up to 110, and it was quite interesting.

    I’m afraid I haven’t got to the level of programing computers for it yet!

    Eileen
    Dedicated Elementary Teacher Overseas (in the Middle East)
    elementaryteacher.wordpress.com

    elementaryteacher

    August 5, 2008 at 1:07 pm

  2. I actually just finished writing a post about my implementation of the sieve of eratosthenes in python after a friend mentioned a problem he had in a physics oriented C programming course. If you’re interested in reading it, it can be found here: http://www.bemasher.net/archives/40

    bemasher

    February 19, 2009 at 11:57 pm

  3. […] primes factorization algorithm with Python the sieve of Eratosthenes a pythonic […]


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: