[Tutor] Can I speed this up?

[Kent Johnson]

Dick,

To get any substantial speedup you will probably have to look at different 
algorithms. It turns out that factoring large numbers is a well-studied 
problem. Googling for 'prime factors algorithm' gives a number of hits 
including these overviews:
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
http://www.frenchfries.net/paul/factoring/theory/index.html

One tweak to your program would be to have isPrime return the factor found; 
in cases where the factor is large that will save some time as you don't 
have to search for it again.

Kent

At 01:27 AM 10/12/2004 -0700, Dick Moores wrote:
>I'd greatly appreciate some tutors taking a look at my factorIntegers.py 
>at <http://www.rcblue.com/Python/factorIntegers-forWeb.py>. I've worked 
>hard to make it as efficient as possible, but suspect there is more that 
>could be done. Or maybe I'm completely on the wrong track as far as speed 
>is concerned.
>
>I've made use of the program to compute prime factors for integers in the 
>5 quintillion range. Please see 
><http://www.rcblue.com/Python/IntegerFactorsForWeb.txt>
>for some results from the latest revision of factorIntegers.py.
>
>You'll note that in almost all cases the primes take the longest time to 
>compute (29 minutes and change). But note also the anomalies listed at the 
>top of the script. Is there something I've missed that would eliminate 
>these? Or are these to be expected, given the nature of the prime factors 
>of these integers?
>
>I also did some computing in the 400 trillion range, and found a bunch of 
>these anomalies. The worst I could find was 42 seconds (primes took 11 
>seconds):
>
>400,000,000,040,471 = 19502713*20509967
>42 seconds
>
>400,000,000,040,507 = 400000000040507 is PRIME
>11 seconds
>
>
>Also, of course, I'd appreciate criticism (or even deserved praise) of 
>anything that catches your wise and experienced eyes.
>
>BTW the line drawn in isPrime(n) at 4,611,600,000,000,000,000 is for my 
>computer and operating system. Yours may require a different line. See the 
>"large number question" Tutor thread of 9/25 and 9/26.
>
>Thanks, tutors.
>
>Dick Moores
>rdm at rcblue.com
>
>Python 2.3.4, Win XP
>
>
>"Few persons have sufficient wisdom to prefer censure, which is useful, to 
>praise which deceives them."
>
>- Francois De La Rochefoucauld
>
>_______________________________________________
>Tutor maillist  -  Tutor at python.org
>http://mail.python.org/mailman/listinfo/tutor