I'd like to have some feedback on this sieve of erasthotones that I've wrote. It outputs all prime numbers up to n correctly (I've tested with the first 10k prime numbers).

Is this well written? Does it look good for python programmers?

I've made the math up to the sqrt of n + 1, which improved the performance a lot.

import time
import sys
from math import sqrt    

def notMarkedValue(n):
    Returns True if parameter is a possible prime number, False otherwise
    return n != -1

def sieve(val):
    Sieve of Eratosthenes implementation. Finds all prime numbers up to n
    primes = [x for x in range(2, val)]
    for n in range(2, int(sqrt(val)+1)):
        if notMarkedValue(n):
            for i in range(2, val):
                index = (i*n) - 2 # shift index down -2 because 0 and 1 are not in the list
                if index < len(primes):
                    primes[index] = -1
    return filter(notMarkedValue, primes)

def saveToFile(primes):
    Saves the input to a file
    with open('output', 'w+') as f:
        for n in primes:
            f.write(str(n) + ' ')

def getMaxNumber():
    Gets, from passed arguments if provided or input otherwise, the number in which all prime numbers up to it will be calculated
    return int(sys.argv[1]) if len(sys.argv) > 1 else int(input('Find all primes up to: '))

def main():
    n = getMaxNumber()
    print("-- counting primes...")
    start = time.clock()
    primes = sieve(n)
    end = time.clock()
    print("-- calculated all prime numbers up to {0} in {1} seconds".format(n, (end - start)))
    print("-- saving to file \"output\"...")

if __name__ == '__main__':

One thing that I've thought was about making def sieve() return a list(filter(notMarkedValue, primes)), so that I'd have a list that could be enumerated later, but I didn't as I thought it'd be a bit overkill.

Edit: Now that I'm thinking of it, I should have added to its docstring that it returns a filter object. :-)


First off, the general naming style in Python is snake_case for functions and variables, and PascalCase for classes. On the note of style, you should also have two blank lines between top-level functions/classes/code blocks.

Secondly, are you sure that you want to be using len( ... ), rather than len ( ... ) - 1, as you did here: if index < len(primes):? The len function "counts" the objects in the list starting at 1, not 0, which means if you're using it to get indexes, it'll be off by one.

Other than that, there's not much else that really needs to be improved here! Good job!

| improve this answer | |
  • \$\begingroup\$ Oh, right, the len(...) issue didn't manifest itself because the first value of the list (2) is already a prime number, but nice catch! Thanks! \$\endgroup\$ – streppel Jul 4 '15 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.