[Tutor] exercise is recursion

Timothy Wilson wilson@visi.com
Mon, 20 Nov 2000 22:09:12 -0600 (CST)


Hi everyone,

I thought I would write a little progam that would factor a given integer
into its primes. This seemed like a good time to use recursion, but I'm
having trouble making it work. Anyone see the problem here? I've added a few
lines of debugging code, and there's a function to determine if a number is
prime, but I don't think I'll need it. Any suggestions would be appreciated.

--snip--
#!/usr/bin/python

# This python factors a number into its primes.

from math import *

def isPrime(number):
	for j in [2] + range(3, sqrt(number)+1, 2):
		if number in [1, 2]:
			return 1
		if  number % j == 0:
			return 0
	return 1

def factor(factors, number, i=2):
	while i < sqrt(number):
		if number % i == 0:
			factor(factors, number/i, i)
			factors.append(i)
#			if number/i == i:
		i = i + 1
	print str(number) + '\t' + str(i) + '\t' + str(factors) # debugging
code
	return factors

def primeFactors(number):
	factors = []
	print 'number' + '\t' + 'i' + '\t' + 'factors' # debugging header
	print str(number) + '\t' + '2' + '\t' + str(factors)
	factor(factors, number)
#	factors.sort()
#	print factors

if __name__ == '__main__':
	number = raw_input('Factor what number into primes? ')
	primeFactors(int(number))

--snip--

Thanks,
Tim

--
Tim Wilson      | Visit Sibley online:         | Check out:
Henry Sibley HS | http://www.isd197.k12.mn.us/ | http://www.zope.org/
W. St. Paul, MN |                              | http://slashdot.org/
wilson@visi.com |   <dtml-var pithy_quote>     | http://linux.com/