Hi, we started doing programing at uni and i got interested so am learning some python at home. just started on generators and thought i'd write a function to generate prime numbers, as you do:

def primes(p=2):
    while True:
        for n in range(2,p):
            if p % n == 0:
                p += 1
                primes(p)
        z = p
        p += 1
        yield z

it does sort out the primes but it also lets a few non-primes through. An example output is:
2 3 5 7 11 13 17 19 23 27 29 31 35 37 41 43 47 53 59 61 67 71 73 79 83 87 89 95 97
as you can see 27, 35, 87 and 95 shouldn't be there.

what i don't get is why it lets these numbers through, i.e. 35, but filters out 15! grrr...

thanks

Edited 6 Years Ago by iloveannaw: n/a

The inner call to primes() does nothing at all. I added a few print statements so that you can see if your program does what you are expecting

def primes(p=2):
    while True:
        for n in range(2,p):
            if p % n == 0:
                p += 1
                print("before calling prime(%d) for n = %d" % (p, n))
                primes(p)
                print("returning from prime(%d) for n = %d" % (p, n))
        z = p
        p += 1
        yield z

prm = primes()

for i in range(15):
    print("found: %d" % next(prm))

thanks!

i got rid of recursion:

def primes(p=2):
    while True:
        flag = 1
        for n in range(2,p/2):
            if p % n == 0:
                flag = 0
                break
        if flag == 1:
            yield p
        p += 1

it's pretty slow though

Edited 6 Years Ago by iloveannaw: n/a

You can speed it up by replacing p/2 by int(math.sqrt(p)+1) (You must write import math first), because a non prime number has a divisor smaller than its square root.

Edited 6 Years Ago by Gribouillis: n/a

This article has been dead for over six months. Start a new discussion instead.