## Sieve of Eratosthenes in Python

Okay, today’s is gonna be a quick one. It’s the Sieve of Eratosthenes in a relatively straightforward way, in Python.

This is actually relatively typical of my usage of Python. It’s not terribly efficient, computationally, since it searches through list many, many times. It’d be relatively easy to use more lines and make the algorithm even more efficient, but that would require more effort and (more importantly) more lines of code. Part of the beauty of Python is its simplicity and conciseness.

def sieve(max): #Takes in a number, and returns all primes between 2 and that number #Start with all of the numbers primes = range(2,max+1) #Start running through each number for i in primes: #Start with double the number, and j = 2 #remove all multiples while i * j <= primes[-1]: #As long as the current multiple of the number #is less than than the last element in the list #If the multiple is in the list, take it out if i * j in primes: primes.remove(i*j) j += 1 return primes

You’d probably be well-served grokking the process, if you haven’t already. To quote my father, “Everyone should understand the Sieve of Eratosthenes.” Plus you’ll probably see it again soon. Next week will probably be the Sieve in one line, thanks to Python. It’s pretty fancy.

print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]

source: http://love-python.blogspot.com/2008/02/find-prime-number-upto-100-nums-range2.html

in comments 🙂

I tried to implement the sieve in python as well and the code is as efficient for list of primes up to ten million as the above is for a list of primes up to ten thousand. Like a thousands times more basically.

def primeSieve(upper):

”’

Generates a list of primes up to upper using the Sieve of Eratosthenes.

”’

primelist = range(0,upper+1)

prime = 2

increment = 4

while prime <= math.sqrt(upper):

while True:

try:

primelist[increment] = 0

increment += prime

except IndexError:

break

while True:

prime += 1

if primelist[prime] != 0:

break

increment = prime * 2

primelist = [x for x in primelist if x != 0]

del primelist[0]

return primelist

Opps, sorry, forgot about indentation not showing up in comments.

def primeSieve(upper):

….”’

….Returns a list of numbers from 0 to upper with non-primes as zero.

….”’

….primelist = range(0,upper+1)

….prime = 2

….inc = 4

….while prime <= math.sqrt(upper):

……..while True:

…………try:

…………….primelist[inc] = 0

…………….inc += prime

…………except IndexError:

…………….break

……..while True:

…………prime += 1

…………if primelist[prime] != 0:

…………….break

……..inc = prime * 2

….primelist = [x for x in primelist if x != 0]

….del primelist[0]

….return primelist

http://docs.python.org/tutorial/controlflow.html#break-and-continue-statements-and-else-clauses-on-loops