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>
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

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