[Tutor] recursive factoring

[Kirby Urner]

At 09:09 PM 1/16/2002 -0800, Kirby Urner wrote:


>>Any suggestions?
>>
>>-Tim
>
>This change to your factor function seems to work:
>
>    def factor(n):
>         if isPrime(n):
>            return [n]
>         for i in range(2, math.sqrt(n)+1):
>            if isPrime(i) and n%i==0:
>                return [i] + factor(n/i)
>
>Kirby
>

OK, one more thing -- isn't the version below more
efficent than the one above?  I don't know for sure.
Seems it would be.


    def factor(n):
         if isPrime(n):
            return [n]
         for i in range(2, math.sqrt(n)+1):
            if isPrime(i) and n%i==0:
                break
         return [i] + factor(n/i)

Kirby