>>>>> Dave Angel <da...@ieee.org> (DA) wrote:
>DA> 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>
>>>
>DA> But if I remember the code, it stopped when the quotient is one, which is
>DA> usually sooner than the square root. And no need to precalculate the
>DA> square root.
That's right. I thought of doing the sqrt trick by testing for num <
factor, i.e."
if num < factor:
break
but found out that it is useless, as for each factor found, num is
divided by that factor as many times as possible. Therefore when the
largest prime factor of num has been found, num ends up being 1 and the
loop stops.
--
Piet van Oostrum <p...@cs.uu.nl>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: p...@vanoostrum.org
--
http://mail.python.org/mailman/listinfo/python-list
