Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!selfless.tophat.at!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.009 X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'else:': 0.03; ':-)': 0.06; 'e.g.,': 0.07; 'python': 0.08; 'from:addr:python': 0.09; 'wrote:': 0.14; 'does,': 0.16; 'enough:': 0.16; 'from:addr:mrabarnett.plus.com': 0.16; 'from:name:mrab': 0.16; 'message-id:@mrabarnett.plus.com': 0.16; 'received:84.92': 0.16; 'received:84.92.122': 0.16; 'received:84.92.122.60': 0.16; 'received:84.93': 0.16; 'received:84.93.230': 0.16; 'reply-to:addr :python-list': 0.16; 'math': 0.16; 'header:In-Reply-To:1': 0.21; 'code': 0.24; 'received:84': 0.25; 'exercise': 0.29; 'import': 0.29; 'instead': 0.29; 'subject:How': 0.30; 'implementing': 0.32; 'does': 0.33; 'to:addr:python-list': 0.33; "isn't": 0.33; 'too': 0.33; 'rather': 0.34; 'chris': 0.34; 'header:User-Agent:1': 0.35; 'curious': 0.35; 'reply-to:addr:python.org': 0.35; 'using': 0.35; 'test': 0.35; 'quite': 0.36; 'subject:can': 0.38; 'but': 0.38; 'skip:9 10': 0.38; 'subject:: ': 0.38; 'some': 0.38; 'doing': 0.39; 'finding': 0.39; 'to:addr:python.org': 0.39; 'skip:1 10': 0.63; 'limit': 0.65; 'header:Reply-To:1': 0.72; 'reply-to:no real name:2**0': 0.72; 'prime': 0.73; 'generator,': 0.84; 'subject:over': 0.84; 'factors': 0.91; 'subject:\t': 0.93 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvgHAJQKAk5UXebj/2dsb2JhbABUhEmTbo5Yd4h1rlWRH4Erg3iBCgSWT4so Date: Wed, 22 Jun 2011 16:33:46 +0100 From: MRAB User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.2.18) Gecko/20110616 Thunderbird/3.1.11 MIME-Version: 1.0 To: python-list@python.org Subject: Re: How can I speed up a script that iterates over a large range (600 billion)? References: In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: python-list@python.org List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 42 NNTP-Posting-Host: 82.94.164.166 X-Trace: 1308756834 news.xs4all.nl 49048 [::ffff:82.94.164.166]:50181 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8216 On 22/06/2011 06:58, Chris Torek wrote: > Now that the exercise has been solved... > > Instead of "really short code to solve the problem", how about > some "really long code"? :-) > > I was curious about implementing prime factorization as a generator, > using a prime-number generator to come up with the factors, and > doing memoization of the generated primes to produce a program that > does what "factor" does, e.g.: > > $ factor 99999999999999999 > 99999999999999999: 3 3 2071723 5363222357 > > The python code is rather too slow for this particular number (I > gave up on it finding 5363222357) but works quite well on 600851475143, > or even, e.g., 12186606004219: > > $ python factor.py 600851475143 12186606004219 > 600851475143: 71 839 1471 6857 > 12186606004219: 2071723 5882353 > [snip] This code isn't particularly efficient, but it's fast enough: import math n = 99999999999999999 limit = math.sqrt(n) test = 2 factors = [] while test <= limit: if n % test == 0: factors.append(test) n //= test limit = math.sqrt(n) else: test += 1 factors.append(n) print(factors)