Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
#!/usr/bin/env python2
''' Eratosthenes sieve
from __future__ import print_function
import array
import time
start = time.time()
limit = 2*10**6 # Four million
sieve = array.array('l',range(limit))
primes = [2] # Start with just first, then append to it
n = 0 # Index into current prime being eliminated
while n*n < limit:
p = primes[n]
# Eliminate all multiples of primes[n]:
for i in range(p+p,limit, p):
sieve[i] = 0
# Find remaining numbers up to new upperbound (current prime squared)
for i in range(primes[-1]+1,min(limit, p*p)): # min() to avoid out of bounds access.
if sieve[i]:
elapsed = start - time.time()
print(', '.join(['%s' % x for x in primes[:20]]), "...",
', '.join(['%s' % x for x in primes[-10:]]))
print("%d primes found in %g seconds" % (len(primes), elapsed))
Copy link

JimDennis commented Jan 5, 2018 for those who want to know more about this algorithm.

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