generator in Python generating prime numbers

Question

I need to generate prime numbers using generator in Python. Here is my code:

def genPrimes():
    yield 2
    x=2
    while True:
        x+=1
        for p in genPrimes():
            if (x%p)==0:
                break
        else:
            yield x

I have a RuntimeError: maximum recursion depth exceeded after the 2nd prime.next() when I run it.

Answer 1

The fastest way to generate primes is with a sieve. Here we use a segmented Sieve of Eratosthenes to generate the primes, one by one with no maximum, in order; ps is the list of sieving primes less than the current maximum and qs is the offset of the smallest multiple of the corresponding ps in the current segment.

def genPrimes():
    def isPrime(n):
        if n % 2 == 0: return n == 2
        d = 3
        while d * d <= n:
            if n % d == 0: return False
            d += 2
        return True
    def init(): # change to Sieve of Eratosthenes
        ps, qs, sieve = [], [], [True] * 50000
        p, m = 3, 0
        while p * p <= 100000:
            if isPrime(p):
                ps.insert(0, p)
                qs.insert(0, p + (p-1) / 2)
                m += 1
            p += 2
        for i in xrange(m):
            for j in xrange(qs[i], 50000, ps[i]):
                sieve[j] = False
        return m, ps, qs, sieve
    def advance(m, ps, qs, sieve, bottom):
        for i in xrange(50000): sieve[i] = True
        for i in xrange(m):
            qs[i] = (qs[i] - 50000) % ps[i]
        p = ps[0] + 2
        while p * p <= bottom + 100000:
            if isPrime(p):
                ps.insert(0, p)
                qs.insert(0, (p*p - bottom - 1)/2)
                m += 1
            p += 2
        for i in xrange(m):
            for j in xrange(qs[i], 50000, ps[i]):
                sieve[j] = False
        return m, ps, qs, sieve
    m, ps, qs, sieve = init()
    bottom, i = 0, 1
    yield 2
    while True:
        if i == 50000:
            bottom = bottom + 100000
            m, ps, qs, sieve = advance(m, ps, qs, sieve, bottom)
            i = 0
        elif sieve[i]:
            yield bottom + i + i + 1
            i += 1
        else: i += 1

A simple isPrime using trial division is sufficient, since it will be limited to the fourth root of n. The segment size 2 * delta is arbitrarily set to 100000. This method requires O(sqrt n) space for the sieving primes plus constant space for the sieve.

It is slower but saves space to generate candidate primes with a wheel and test the candidates for primality with an isPrime based on strong pseudoprime tests to bases 2, 7, and 61; this is valid to 2^32.

def genPrimes(): # valid to 2^32
    def isPrime(n):
        def isSpsp(n, a):
            d, s = n-1, 0
            while d % 2 == 0:
                d /= 2; s += 1
            t = pow(a,d,n)
            if t == 1: return True
            while s > 0:
                if t == n-1: return True
                t = (t*t) % n; s -= 1
            return False
        for p in [2, 7, 61]:
            if n % p == 0: return n == p
            if not isSpsp(n, p): return False
        return True
    w, wheel = 0, [1,2,2,4,2,4,2,4,6,2,6,4,2,4,\
        6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,\
        2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
    p = 2; yield p
    while True:
        p = p + wheel[w]
        w = 4 if w == 51 else w + 1
        if isPrime(p): yield p

If you're interested in programming with prime numbers, I modestly recommend this essay at my blog.