# Pythonic sieve of Erasthotones that saves results to file

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\"...")
saveToFile(primes)

if __name__ == '__main__':
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.
• 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! Jul 4, 2015 at 20:26