Skip to content

Instantly share code, notes, and snippets.

Created Dec 7, 2014
What would you like to do?
infinite sequence of primes generator in Python (unbounded Sieve of Eratosthenes)
def primes():
prime_multiple_factors = {}
def add_factor(composite, factor):
if composite not in prime_multiple_factors:
prime_multiple_factors[composite] = set([factor])
x = 2
while True:
if x in prime_multiple_factors:
for factor in prime_multiple_factors[x]:
add_factor(x + factor, factor)
del prime_multiple_factors[x]
add_factor(x * 2, x)
yield x
x += 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment