[Tutor] Can I speed this up?

[Dick Moores]

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