Generator function for prime numbers

Question

I'm trying to write a generator function for printing prime numbers as follows

 def getPrimes(n):
    prime=True
    i=2
    while(i<n):
        for a in range(2,i):
            if(i%a==0):
                prime=False
                break
        if(prime):    
            yield i

However I'm not getting the desired results p=getPrimes(100) should give me a generator function that will iterate primes from 2 through 100 but the result I'm getting is [2,3]. What am I doing wrong?

Answer 1

Sieve of Eratosthenes: Most efficient prime generator algorithm

Taken from here:

Simple Prime Generator in Python - an answer by Eli Bendersky.

It marks off all the multiples of 2, 3, 5, 7 and 11. The rest are all prime numbers.

def genprimes(limit): # derived from 
                      # Code by David Eppstein, UC Irvine, 28 Feb 2002
    D = {}            # http://code.activestate.com/recipes/117119/
    q = 2

    while q <= limit:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1

p = genprimes(100)
prms = [i for i in p]

print prms

Output:

[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]

Answer 2

You need to reset prime to True as the first statement inside the while block, not before it. As it is, once you hit a single composite number, prime will never be true again, so you'll never yield any more numbers.

Answer 3

You have a couple of errors, see the comments:

def getPrimes(n):
    i = 2
    while i < n :
        prime = True # reset the `prime` variable before the inner loop
        for a in xrange(2, i):
            if i%a == 0:
                prime = False
                break
        if prime:    
            yield i
        i += 1 # don't forget to advance `i`

Now for a better implementation that handles correctly the edge cases, performs a great deal less iterations and generates a sequence of the prime numbers less than the value of the n parameter:

def getPrimes(n):
    if n <= 2:
        raise StopIteration
    yield 2
    for i in xrange(3, n, 2):
        for x in xrange(3, int(i**0.5)+2, 2):
            if not i % x:
                break
        else:
            yield i

Either way, the code works as expected:

[x for x in getPrimes(20)]
=> [2, 3, 5, 7, 11, 13, 17, 19]

Answer 4

def isprime(n):
    for i in range(2 ,int((n**0.5))+1):
        if n % i == 0:
            return False
    return True

def getPrimes(n):
    yield 2
    i = 1
    while i <= n-2:
        i += 2
        if isprime(i):
            yield i

Answer 5

As Istvan Chung answered, your issue comes from the fact that you don't ever reset your prime flag. However, rather than fixing that issue directly, I suggest an alternative solution.

Rather than using a flag variable to detect when you've made it all the way through the loop without hitting a break, use an else block after the loop:

def getPrimes(n):
    i = 2
    while i < n :
        for a in range(2, i):
            if i % a == 0:
                break
        else:    
            yield i

The else block will be run if the loop completes, rather than being stopped early by a break statement.

You could probably improve this further by only testing prime divisors, rather than all integers less than i. Here's a way to do that with recursion (an alternative is to keep a list of the previously computed primes, but that may require a lot of storage space if n is very large):

def getPrimes(n):
    yield 2
    i = 3
    while i < n:
        for a in getPrimes(int(math.sqrt(i))+1):
            if i % a == 0:
                break
        else:
            yield i
        i += 2