[Tutor] recursive factoring

[mikalzet@libero.it]

On Wed, 16 Jan 2002, Tim Wilson wrote:

> 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. :-)

Well, I have taken a look at all the recursive solutions proposed.
My impression is that a non-recursive solution would be simpler and more
efficient.

What do you people think of:

def primeNumber(n):
	if n==1: return 1
	a = []
	b = 2
     	while b <= n:
	             while n % b == 0:
		                     a.append(b)
		                     n = n/b
		     b = b + 1
        return a


I've tried it and it seems to work well.

-- 
Michele Alzetta