On 23/08/12 02:17, Richard D. Moores wrote:
I've incorporated many of the suggestions I've received here.
Here's a function, factor_integer(), for quickly factoring any integer
up to 1e17:<http://pastebin.com/BLfV0EMw>.
That relies on a pre-existing cache of prime numbers. If you don't use
those cached prime numbers, do you know how long your code takes?
Larger integers will be factored eventually -- the wait can be long or
short. Probably long if they require the services of lines 82-91.
Examples of extremes, both between 1e25 and 1e26:
2,835,334,663,465,375,591,838,337 [3, 19, 37, 71, 947,
19994908447741489] 1.172 secs
9,349,337,574,247,205,482,125,105 [3, 5, 2027, 2311296661,
133039358281] 402.5 secs
I'm astounded by the times you quote there.
The first example includes the prime 19994908447741489, which is *not*
in the cache, since it is bigger than 1e17. And yet it only takes about
a second to find all six primes. If true, that's astonishingly good for
something written in pure Python.
The second example includes the prime 133039358281, which is smaller
than 1e17 and so should be in the cache and therefore found (almost)
instantly. And yet you claim it takes nearly seven minutes to find it.
If correct, that's astonishingly awful given that you have the prime
numbers already cached.
Can you explain those timings? How did you measure them?
--
Steven
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
