Skip to content

Instantly share code, notes, and snippets.

@dpk dpk/primesieve.py
Created Dec 7, 2014

Embed
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])
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
You can’t perform that action at this time.