Eratosthenes method to find primes

Question

Illustrate the sieve of eratosthenes method to find out prime numbers.

Solution

def eratosthenes():
    D = {}
    q = 2
    while True:
        p = D.pop(q, None)
        if p:
            x = p + q
            while x in D:
                x += p
            D[x] = p
        else:
            D[q*q] = q
            yield q
        q += 1

Run this
Comments by Disqus