## More about primes…The Sieve of Eratosthenes

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.

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

elementaryteacherAugust 5, 2008 at 1:07 pm

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

bemasherFebruary 19, 2009 at 11:57 pm

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

Prime Factorization « PythonismFebruary 26, 2009 at 3:29 pm