Re: Any Better logic for this problem..

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From	Gregory Ewing <greg.ewing@canterbury.ac.nz>
Newsgroups	comp.lang.python
Subject	Re: Any Better logic for this problem..
Date	Fri, 10 Jun 2011 10:39:53 +1200
Lines	14
Message-ID	<95d0drFa9jU1@mid.individual.net> (permalink)
References	<BANLkTinWq5pjX2+0OVRvm1Xs7ESmYf0qcw@mail.gmail.com> <BANLkTimicVsm7EGMsVu0bXRsa7714MKpwA@mail.gmail.com> <mailman.48.1307611509.11593.python-list@python.org>
Mime-Version	1.0
Content-Type	text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding	7bit
X-Trace	individual.net ppn9eRYOrAmx+eRY1HFBOgDSyQYZwIJokWw00naoBlqsUd7HlP
Cancel-Lock	sha1:XGjdwCfppQ6EhqOvWPLgfspErEw=
User-Agent	Mozilla Thunderbird 1.0.5 (Macintosh/20050711)
X-Accept-Language	en-us, en
In-Reply-To	<mailman.48.1307611509.11593.python-list@python.org>
Xref	x330-a1.tempe.blueboxinc.net comp.lang.python:7325

Show key headers only | View raw

Chris Angelico wrote:

> Rather than find all prime numbers up to num, stop at sqrt(num) - it's
> not possible to have any prime factors larger than that.

That's not quite true -- the prime factors of 26 are 2 and 13,
and 13 is clearly greater than sqrt(26).

However, once you've divided out all the primes up to sqrt(n),
whatever is left, if greater than 1, must itself be prime, so
you can add it to your prime factors and stop.

-- 
Greg

Thread

Re: Any Better logic for this problem.. Chris Angelico <rosuav@gmail.com> - 2011-06-09 19:25 +1000
  Re: Any Better logic for this problem.. Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-06-10 10:39 +1200
    Re: Any Better logic for this problem.. Chris Angelico <rosuav@gmail.com> - 2011-06-10 08:44 +1000

csiph-web