MRAB wrote:
<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:
[snip]
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
recalculate
the square root when num changes (expensive calculation vs smaller
search space).
</div>
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.
</div>
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.
--
http://mail.python.org/mailman/listinfo/python-list
