Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!selfless.tophat.at!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <ian.g.kelly@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.073
X-Spam-Evidence: '*H*': 0.86; '*S*': 0.00; 'check.': 0.07; 'python': 0.08; '21,': 0.09; 'pm,': 0.10; 'wrote:': 0.14; 'careful,': 0.16; 'division,': 0.16; 'subject: \n ': 0.16; 'subject:was': 0.16; 'cc:addr:python-list': 0.17; 'tue,': 0.17; 'header:In-Reply-To:1': 0.21; "wasn't": 0.22; 'cc:2**0': 0.22; 'cc:no real name:2**0': 0.23; 'received:209.85.161.46': 0.23; 'received:mail- fx0-f46.google.com': 0.23; 'function': 0.25; 'changed': 0.25; 'received:209.85.161': 0.26; "i'm": 0.27; 'message- id:@mail.gmail.com': 0.28; 'problem': 0.28; 'bound': 0.29; 'subject:How': 0.30; 'cc:addr:python.org': 0.30; 'iterating': 0.30; 'actually': 0.33; 'however,': 0.34; 'yours!': 0.35; 'received:google.com': 0.37; 'received:209.85': 0.37; 'page': 0.37; 'problem.': 0.38; 'subject:can': 0.38; 'but': 0.38; 'question,': 0.38; 'subject:: ': 0.38; 'subject: (': 0.39; 'received:209': 0.39; 'finding': 0.39; 'subject:, ': 0.60; 'john': 0.62; 'subject:. ': 0.65; 'square': 0.67; 'prime': 0.73; 'trial': 0.76; '3:09': 0.84; 'subject:over': 0.84; 'worry,': 0.84; 'yielded': 0.84; 'unclear': 0.91; 'subject:much': 0.93; 'greatest': 0.95
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=MhPsYLhA3wxeYMEKW4pIZw0ZwC0VT7T5v17UFZFwRVE=; b=YckoztY+rNuVTYdfNRXbNE9y0W8HBifC59OWMGOGOzMqcICeV1IZArqhhalbrcHK0Q vr/r8NDuGb0A2dc0IvgTz9NBIpjC8YJYK+C4FDl+iAgkRQJooaEU+1J4hj74o4QOrDpv Wh5Wr9KJmptRL/y8YCGSht9UldxTJQanC8+gk=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; b=d+ksVSrqgKgtywm+4CK04NP29CAtMbUAEyf4QjsIDRsZ605I/q19HeRnQu5pUde1qM Lt58xbIw05OldZv4353b6KDIQIi0MftzKRtaLcfxMILPKfxB2CQ4KmEzgIQiojE5XD1B ND3hpgu1lQFDolkz81pNRZuZbJiSX3NFgP1fI=
MIME-Version: 1.0
In-Reply-To: <8b8c4bc8-7b26-4113-b95b-7eccbbd0e901@q30g2000yqb.googlegroups.com>
References: <f97b3159-318a-41e2-9f28-339fa4a81d79@k6g2000yqc.googlegroups.com> <4e00faa9$0$49180$e4fe514c@news.xs4all.nl> <4e00fd85$0$49038$e4fe514c@news.xs4all.nl> <8b8c4bc8-7b26-4113-b95b-7eccbbd0e901@q30g2000yqb.googlegroups.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Tue, 21 Jun 2011 15:41:53 -0600
Subject: Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
To: John Salerno <johnjsal@gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Cc: python-list@python.org
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.245.1308692544.1164.python-list@python.org>
Lines: 17
NNTP-Posting-Host: 82.94.164.166
X-Trace: 1308692544 news.xs4all.nl 49184 [::ffff:82.94.164.166]:35402
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8135

On Tue, Jun 21, 2011 at 3:09 PM, John Salerno <johnjsal@gmail.com> wrote:
> Don't worry, I was still unclear about what to do after reading all
> the responses, even yours! But one thing that made me feel better was
> that I wasn't having a Python problem as much as a *math* problem. I
> changed my get_factors function to only go as far as the square root
> of the number in question, and that yielded an answer immediately. :)
>
> However, even after reading the Wikipedia page about prime numbers and
> trial division, I'm still a little unclear as to why the square root
> of the number is the upper bound of the range you need to check.

Careful, note that the greatest prime factor may actually be greater
than the square root.  It's just that it's possible to find it without
iterating past the square root.  This is because for each p that is a
factor of n, q is also a factor of n, where p * q = n.  If p >
sqrt(n), then q < sqrt(n).  Therefore you can find p by finding q and
dividing n / q.