Generator Of Prime Numbers In Python

I try to create the stream of all prime numbers in Python using the steve of Eratosthenes. However, I get an error. Here is what I tried: def genPrimes0(N): if (isPrime(N)):

Solution 1:

I think you're trying too hard in your current generator. You can get away with doing much less work (e.g. having an isPrime oracle) and just letting the algorithm do its thing:

def primes(n=2): # don't provide a different n value, or you will get odd results
    yield n
    yield from filter(lambda x: x % n, primes(n+1))

That uses some Python 3.3 specific syntax (yield from), but you can do an equivalent generator for earlier versions just by making it an explicit loop over the filter's results. @icktoofay's answer shows that kind of loop (and he also points out that filter is only a generator in Python 3, so use itertools.ifilter if you're using Python 2).

Example output:

>>> for p in primes():
    print(p)
    if p > 100:
        break


2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101

Solution 2:

You don't need recursive for lazy evaluation, you can use functions from itertools to calculate primes lazily.

import itertools    

def primes():
    numbers = itertools.count(2)
    while True:
        p = numbers.next()
        numbers = itertools.ifilter(lambda x, p=p: x%p, numbers)
        yield p

print list(itertools.islice(primes(), 100))

Solution 3:

This is not Eratosthenes, but som non tail recursiv function witch just fills stack. If you have isPrime function you should write like

def gen_primes(start):
   return itertools.filter(isPrime , itertools.count(start) )