Skip to content

Instantly share code, notes, and snippets.

@willtownes
Created December 6, 2011 01:43
Show Gist options
  • Save willtownes/1436308 to your computer and use it in GitHub Desktop.
Save willtownes/1436308 to your computer and use it in GitHub Desktop.
Faster way to list primes in Python
def listprimes2(m):
'''another attempt to list all primes below m'''
values = range(m+1) #note that in this list the key and the value are the same.
primes = values[:]
primes[1] = 0 #1 doesn't count as a prime
for i in values:
if primes[i] == 0:
pass
else:
for j in values[i+1:]:
if primes[j]==0 or primes[j]%i != 0:
pass
else:
primes[j] = 0
return primes
import time
tstart = time.time()
ans = sum(listprimes2(2000000))
telapsed = time.time()-tstart
@willtownes
Copy link
Author

It took about 37 seconds to execute. I know it's not perfect, but at least got the right answer.

@willtownes
Copy link
Author

thanks John!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment