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:

defprimes(n=2): # don't provide a different n value, or you will get odd resultsyield n
    yieldfromfilter(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:
        break2357111317192329313741434753596167717379838997101

Solution 2:

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

import itertools    

defprimes():
    numbers = itertools.count(2)
    whileTrue:
        p = numbers.next()
        numbers = itertools.ifilter(lambda x, p=p: x%p, numbers)
        yield p

printlist(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

defgen_primes(start):
   return itertools.filter(isPrime , itertools.count(start) )