processing limitation in Python

[Tim Peters]

[pdr14 at comcast.net]
> If I un-comment any line in this program below the line where I
> commented " all OK up to this point " This program locks up my
> computer.
>
> Windows task manager will show "Not Responding" for Python in the
> Applications tab and in the Performance tabe the CPU usage will be
> locked at %100.
>
> I've experienced the same problem on 2 different computers, one running
> 2000 pro. the other running XP home eddition.  both computers run
> Python 2.4.2
>
> I'm just wondering if any one else has noticed any problems with
> working with large numbers in Python ind if there is anything that can
> work around this issue.
>
> Thankd for reading
> David
>
> def factor(n):
>     d = 2
>     factors = [ ]
>     while n > 1:
>         if n % d == 0:
>             factors.append(d)
>             n = n/d
>         else:
>             d = d + 1
>     print factors

You primary problem is that this is a horridly inefficient way to
factor, taking time propotional to n's largest prime divisor (which
may be n).

> factor (12)
> factor (123)
> factor (1234)
> factor (12345)
> factor (123456)
> factor (1234567)
> factor (12345678)
> factor (123456789)
> factor (1234567898)
> factor (12345678987)
> factor (123456789876)
> factor (1234567898765)       # all OK up to this point
> #factor (12345678987654)    # locks up computer if I run this line

It doesn't lock up for me, using Python 2.3.5 or 2.4.2 on Windows (XP
Pro SP2, but the specific flavor of Windows shouldn't matter).  I ran
it from a DOS box, and while it was plugging away on 12345678987654,
hitting Ctrl+C stopped it.

If you let it continue running, and you & your computer were immortal
(something worth shooting for :-)), it would eventually print the
factorization.  Since

    12345678987654 = 2 * 3 * 2057613164609

the loop would have to go around over 2 trillion times to find the
final 2057613164609 prime factor.  A simple enormous improvement is to
get out of the loop when d*d > n.  Then n must be prime or 1.  That
would slash the worst-care runtime from being proportional to n to
being proportional to sqrt(n).

> ...