Skip to content

Instantly share code, notes, and snippets.

@dpk
Created December 7, 2014 23:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dpk/536aa9fd76f7237795db to your computer and use it in GitHub Desktop.
Save dpk/536aa9fd76f7237795db to your computer and use it in GitHub Desktop.
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])
else:
prime_multiple_factors[composite].add(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]
else:
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