Home > Code Dump > Sieve of Eratosthenes in Python

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.

Advertisements
Categories: Code Dump
  1. April 12, 2010 at 2:23 pm

    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 🙂

  2. February 25, 2012 at 9:01 am

    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

  3. February 25, 2012 at 9:15 am

    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

  4. GVR
  1. March 3, 2009 at 7:28 pm
  2. July 23, 2011 at 12:17 am

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: