Skip to content

Instantly share code, notes, and snippets.

Created December 7, 2014 23:47
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