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. :-)