Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!xlned.com!feeder5.xlned.com!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!newsgate.cistron.nl!newsgate.news.xs4all.nl!194.109.133.85.MISMATCH!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!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.007
X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; "(i'm": 0.09; '21,': 0.09; 'through.': 0.09; 'pm,': 0.10; 'def': 0.12; 'wrote:': 0.14; '1),': 0.16; '1:48': 0.16; 'answer,': 0.16; 'iterated': 0.16; 'n):': 0.16; 'shorten': 0.16; '\xa0for': 0.16; 'cc:addr:python-list': 0.17; 'tue,': 0.17; 'cheers,': 0.19; 'header:In-Reply-To:1': 0.21; 'cc:2**0': 0.22; 'cc:no real name:2**0': 0.23; '\xa0if': 0.23; 'received:209.85.161.46': 0.23; 'received:mail- fx0-f46.google.com': 0.23; 'function': 0.25; 'received:209.85.161': 0.26; 'testing': 0.27; 'tried': 0.27; 'message-id:@mail.gmail.com': 0.28; 'far.': 0.29; 'subject:How': 0.30; 'cc:addr:python.org': 0.30; "can't": 0.32; 'itself,': 0.35; 'quite': 0.36; 'optimization': 0.37; 'similar': 0.37; 'received:google.com': 0.37; 'received:209.85': 0.37; 'could': 0.38; 'subject:can': 0.38; 'but': 0.38; 'subject:: ': 0.38; '8bit%:6': 0.39; 'doing': 0.39; 'subject: (': 0.39; 'received:209': 0.39; 'initially': 0.39; 'john': 0.62; 'further': 0.65; 'here': 0.66; 'billion': 0.67; 'magnitude,': 0.84; 'subject:over': 0.84
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:content-transfer-encoding; bh=N2gG8hE/HNP1b08fcGEmcgAv89+Ng9MSzKcHASilMmA=; b=CZDMS14sY9tXxIDY36JpUKyMpPp2EUY1i3yXwPsn6JMxIl+fFxjHhTqjaTJRkFH/kU K1L9kUeMeAYGb0vJ/+472O8haGxLgJSnBid8WOYA+DXcRtBpJRkd4KEFANa9xjKH3CbZ MZj6cbD17Hw7De1opBS+ZtZtvyRyCehkjLjpo=
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:content-transfer-encoding; b=K5dxznv8btD6pjyj8e3bnf8CZqSx4ve7pI4bh8vP4hIQT3TN/KePza4tXjgIpWKvit fHg0cV/pAeIbjk2sVq0hDJRsd43xXtKCYsQsqL3epq5iwJFCbFEdqkw0a7MXyvOd9WYp TZhpL1/7ueFTWlFPOT46FQf8ziIE2cne5hGFc=
MIME-Version: 1.0
In-Reply-To: <f97b3159-318a-41e2-9f28-339fa4a81d79@k6g2000yqc.googlegroups.com>
References: <f97b3159-318a-41e2-9f28-339fa4a81d79@k6g2000yqc.googlegroups.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Tue, 21 Jun 2011 14:02:21 -0600
Subject: 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
Content-Transfer-Encoding: quoted-printable
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.242.1308686573.1164.python-list@python.org>
Lines: 27
NNTP-Posting-Host: 82.94.164.166
X-Trace: 1308686573 news.xs4all.nl 49179 [::ffff:82.94.164.166]:35160
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8120

On Tue, Jun 21, 2011 at 1:48 PM, John Salerno <johnjsal@gmail.com> wrote:
> Here is what I have so far. Initially the get_factors function just
> iterated over the entire range(2, n + 1), but since a number can't
> have a factor greater than half of itself, I tried to shorten the
> range by doing range(2, n //2), but that still leaves 300 billion
> numbers to go through.

Without giving you the answer, I will note that the range can be
further reduced by quite a lot (I'm talking orders of magnitude, not
just by half).

> def get_primes(number_list):
> =A0 =A0primes =3D number_list[:]
>
> =A0 =A0for n in number_list:
> =A0 =A0 =A0 =A0for x in range(2, n):
> =A0 =A0 =A0 =A0 =A0 =A0if n % x =3D=3D 0:
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0primes.remove(n)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0break
>
> =A0 =A0return primes

Also, primality testing and factorization are very similar problems,
and the same range optimization could be applied here as well.

Cheers,
Ian