Why is my code faster with append() in a loop than with a large list?
davea at ieee.org
Mon Jul 6 20:28:05 CEST 2009
> <div class="moz-text-flowed" style="font-family: -moz-fixed">Dave
> Angel wrote:
>> MRAB wrote:
>>> <div class="moz-text-flowed" style="font-family: -moz-fixed">Dave
>>> Angel wrote:
>>>> It would probably save some time to not bother storing the zeroes
>>>> in the list at all. And it should help if you were to step through
>>>> a list of primes, rather than trying every possible int. Or at
>>>> least constrain yourself to odd numbers (after the initial case of 2).
>>> Or stop looking for more factors when you've passed the square root of
>>> num. I don't know what effect there'll be on the time if you
>>> the square root when num changes (expensive calculation vs smaller
>>> search space).
>> But if I remember the code, it stopped when the quotient is one,
>> which is usually sooner than the square root. And no need to
>> precalculate the square root.
> If the number is a large prime then the code will try all the numbers up
> to that, eg if num == 1000003 then it'll try 2..1000003 even though it
> could've given up after 1000.
That's one reason I suggested (and Piet implemented) a sieve. You can
stop dividing when the square of the next prime exceeds your quotient.
More information about the Python-list