[Tutor] recursive factoring
Tim Wilson
wilson@visi.com
Wed, 16 Jan 2002 22:38:01 -0600 (CST)
Hi everyone,
I've been trying to write a little function that will generate a list of
all the prime factors of a given integer. This seems like the sort of
problem that maps very well to a recursive algorithm. Take the prime
factors of 24 for example:
24
/ \
2 12
/ \
2 6
/ \
2 3
The prime factors are 2, 2, 2, and 3. If that isn't recursion waiting to
happen, I don't know what is. :-)
Unfortunately, I can't get my function to work. I just don't grok
recursion. Here's what I've tried (one version of it anyway):
import math
def isPrime(n):
if n in [1, 2]: return 1
for i in [2] + range(3, math.sqrt(n)+1, 2):
if n % i == 0:
return 0
return 1
def factor(n, factors=[]):
if isPrime(n):
factors.append(n)
return factors
else:
for i in range(2, math.sqrt(n)+1):
if n % i == 0:
factor(n/i, factors)
This is quite broken (it returns 'None'), but I hope you can see where I
was headed.
Any suggestions?
-Tim
--
Tim Wilson | Visit Sibley online: | Check out:
Henry Sibley HS | http://www.isd197.org | http://www.zope.com
W. St. Paul, MN | | http://slashdot.org
wilson@visi.com | <dtml-var pithy_quote> | http://linux.com