Skip to content

Instantly share code, notes, and snippets.

@gmcclure
Created April 27, 2013 23:14
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save gmcclure/5475130 to your computer and use it in GitHub Desktop.
Praxis, Sieve of Eratosthenes
# sieve of eratosthenes
import math
import time
class Sieve(object):
def find_primes_to_max(self, n):
n += 1
primes_filter = [0] * n
primes_filter[0] = 1
primes_filter[1] = 1
limit = int(math.sqrt(n))
for i in range(3, limit, 2):
start = i*i
for x in range(start, n, i):
primes_filter[x] = 1
primes = [2]
for n in range(3, n, 2):
if not primes_filter[n]:
primes.append(n)
return primes
if __name__ == '__main__':
start = time.time()
s = Sieve()
print len(s.find_primes_to_max(15485863))
elapsed = (time.time() - start)
print "Elapsed time: ", elapsed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment