On 1/05/2006 2:52 PM, [EMAIL PROTECTED] 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]
>>>
"""
--
http://mail.python.org/mailman/listinfo/python-list
