Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import time
def primes(n):
if n==2:
return [2]
elif n<2:
return []
s=range(3,n+1,2)
mroot = n ** 0.5
half=(n+1)/2-1
i=0
m=3
while m <= mroot:
if s[i]:
j=(m*m-3)/2
s[j]=0
while j<half:
s[j]=0
j+=m
i=i+1
m=2*i+3
return [2]+[x for x in s if x]
def benchmark():
start = time.time()
for _ in xrange(40):
count = len(primes(1000000))
end = time.time()
print "Benchmark duration: %r seconds" % (end-start)
benchmark()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.