On 1/05/2006 2:52 PM,

(E-Mail Removed) wrote:

> hello, i have another problem i feel that i have to be missing

> something.. Basically, i've written a recursive function to find all

> the prime up to a number (lim).. here is the function:

>

> The function basically takes in a list of all the prime number found,

> it takes the next number to be tested for (next) and the limit it will

> go up to. It divide next by the list of previous prime numbers if next

> is not bigger than lim, count up all the times where it's not evenly

> divdided, if the result is equal the length of prime number, then we

> have another prime number, lather rinse and repeat

>

> def findPrime(seed, next, lim):

> print("seed: " + str(seed) + " next: " + str(next) + " lim: " +

> str(lim))

> print(seed)

> if(next >= lim):

> print(seed)

> return seed

> else:

> count = 0;

> for num in seed:

> modu = math.modf(float(next)/float(num));

> if(modu[0] > 0):

> count += 1

> if(count == len(seed)):

> seed.append(next)

> findPrime(seed, next+2, lim)

> else:

> findPrime(seed, next+2, lim)

>

> As you can probably see, i've printed the value of seed up until the

> point where i'm returning the seed, however, the function still returns

> None..

>
That's because it "falls off the end" of the function, which causes it

to return None. However that's not your only problem. Major other

problem is updating "seed" in situ.

Consider the following:

=== file: pseed.py ===

def findPrime(seed, next, lim):

print "seed: %r, next: %d, lim: %d" % (seed, next, lim)

if next >= lim:

return seed

for num in seed:

# modu = math.modf(float(next)/float(num));

# Try integer arithmetic:

if num > 2 and not (next % num):

# "next" is not a prime number

return findPrime(seed, next+2, lim)

return findPrime(seed + [next], next+2, lim)

# results:

"""

>>> pseed.findPrime([1, 2], 3, 30)
seed: [1, 2], next: 3, lim: 30

seed: [1, 2, 3], next: 5, lim: 30

seed: [1, 2, 3, 5], next: 7, lim: 30

seed: [1, 2, 3, 5, 7], next: 9, lim: 30

seed: [1, 2, 3, 5, 7], next: 11, lim: 30

seed: [1, 2, 3, 5, 7, 11], next: 13, lim: 30

seed: [1, 2, 3, 5, 7, 11, 13], next: 15, lim: 30

seed: [1, 2, 3, 5, 7, 11, 13], next: 17, lim: 30

seed: [1, 2, 3, 5, 7, 11, 13, 17], next: 19, lim: 30

seed: [1, 2, 3, 5, 7, 11, 13, 17, 19], next: 21, lim: 30

seed: [1, 2, 3, 5, 7, 11, 13, 17, 19], next: 23, lim: 30

seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 25, lim: 30

seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 27, lim: 30

seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 29, lim: 30

seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29], next: 31, lim: 30

[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

>>>
"""

# Doh! Looks like recursion not necessary. Google 'eliminate tail

recursion'

def findPrime2(lim):

seed = [1, 2]

for next in xrange(3, lim, 2):

prime = True

for num in seed:

if num > 2 and not (next % num):

prime = False

break

if prime:

seed.append(next)

return seed

# results:

"""

>>> pseed.findPrime2(30)
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

>>>
"""