Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed6.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.095 X-Spam-Evidence: '*H*': 0.81; '*S*': 0.00; ':-)': 0.06; 'answer?': 0.09; 'from:addr:python': 0.09; 'naturally': 0.09; 'written': 0.14; 'wrote:': 0.14; '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; 'reply-to:addr:python-list': 0.16; 'algorithm': 0.16; 'header:In-Reply-To:1': 0.21; "haven't": 0.22; 'say,': 0.22; 'fine': 0.22; 'smallest': 0.23; 'received:84': 0.25; 'function': 0.25; "i'm": 0.27; 'problem': 0.28; 'subject:How': 0.30; 'second': 0.30; 'yet': 0.32; 'to:addr:python-list': 0.33; 'list': 0.33; 'actually': 0.33; 'project': 0.33; 'list.': 0.33; "i've": 0.33; 'header:User-Agent:1': 0.35; 'exercises': 0.35; 'reply-to:addr:python.org': 0.35; 'several': 0.36; 'takes': 0.37; 'another': 0.37; 'largest': 0.38; 'subject:can': 0.38; 'but': 0.38; 'subject:: ': 0.38; 'doing': 0.39; 'should': 0.39; 'feed': 0.39; 'number,': 0.39; 'difficult': 0.39; 'to:addr:python.org': 0.39; 'more': 0.60; 'powered': 0.62; 'john': 0.62; 'according': 0.63; 'design': 0.63; 'designed': 0.65; '"what': 0.67; 'header :Reply-To:1': 0.72; 'reply-to:no real name:2**0': 0.72; 'obtained': 0.73; 'prime': 0.73; 'website:': 0.75; 'canceling': 0.84; 'repeat.': 0.84; 'subject:over': 0.84; 'factors': 0.91; 'subject:\t': 0.93; 'absolutely': 0.98 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtcHABf9AE7Unw4S/2dsb2JhbABUmCiOU3eIdb9VhioElkiLJQ Date: Tue, 21 Jun 2011 21:26:48 +0100 From: MRAB User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.2.17) Gecko/20110414 Thunderbird/3.1.10 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=ISO-8859-1; 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: 30 NNTP-Posting-Host: 82.94.164.166 X-Trace: 1308688012 news.xs4all.nl 49179 [::ffff:82.94.164.166]:35529 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8126 On 21/06/2011 20:48, John Salerno wrote: > I'm working on the Project Euler exercises and I'm stumped on problem > 3: > > "What is the largest prime factor of the number 600851475143 ?" > > Now, I've actually written functions to get a list of the factors of > any given number, and then another function to get the prime numbers > from that list. It works fine with small numbers, but when I try to > feed my get_factors function with the above number (600 billion), > naturally it takes forever! But according to the Project Euler > website: > > "I've written my program but should it take days to get to the answer? > > Absolutely not! Each problem has been designed according to a "one- > minute rule", which means that although it may take several hours to > design a successful algorithm with more difficult problems, an > efficient implementation will allow a solution to be obtained on a > modestly powered computer in less than one minute." > > But it definitely takes more than a minute, and I still haven't gotten > it to end yet without just canceling it myself. > [snip] A non-prime is the product of a prime and another number which may or may not be a prime. Look for the smallest prime and repeat. On a modern PC, if it takes more than, say, a second for the given number, you're doing it wrong. :-)