Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!goblin1!goblin2!goblin.stu.neva.ru!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.024 X-Spam-Evidence: '*H*': 0.95; '*S*': 0.00; 'attempting': 0.04; 'googled': 0.09; 'iterate': 0.09; 'received:81.103': 0.09; 'received:81.103.221': 0.09; 'received:81.103.221.35': 0.09; 'received:ispmail.ntl.com': 0.09; 'received:ntl.com': 0.09; 'wrote:': 0.14; 'computation': 0.16; 'from:addr:hobson42': 0.16; 'from:name:ian': 0.16; 'received:192.168.0.12': 0.16; 'received:aamtaout02-winn.ispmail.ntl.com': 0.16; 'algorithm': 0.16; 'header:In-Reply-To:1': 0.21; 'creating': 0.24; 'code': 0.24; 'function': 0.25; "i'm": 0.27; 'work.': 0.28; 'wondering': 0.28; 'changing': 0.28; 'e.g.': 0.29; "won't": 0.30; '(so': 0.30; 'this.': 0.31; 'does': 0.33; 'to:addr:python-list': 0.33; 'list': 0.33; 'file': 0.34; 'that,': 0.34; 'there': 0.35; 'header:User- Agent:1': 0.35; 'else': 0.35; 'message-id:@gmail.com': 0.36; 'bigger': 0.37; 'largest': 0.38; 'url:org': 0.38; 'subject:: ': 0.38; 'received:192': 0.38; 'goes': 0.39; 'to:addr:python.org': 0.39; 'appreciated.': 0.40; 'simply': 0.60; 'stop': 0.62; 'order': 0.62; 'our': 0.63; 'square': 0.67; 'become': 0.72; 'prime': 0.73; 'subject:this': 0.76; 'subject:..': 0.82; 'bigger,': 0.84; 'divides': 0.84; 'num': 0.84; 'factors': 0.91 Date: Thu, 09 Jun 2011 10:19:52 +0100 From: Ian User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.1; en-GB; rv:1.9.2.17) Gecko/20110414 Lightning/1.0b2 Mnenhy/0.8.3 Thunderbird/3.1.10 MIME-Version: 1.0 To: python-list@python.org Subject: Re: Any Better logic for this problem.. References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Cloudmark-Analysis: v=1.1 cv=R50lirqlHffDPPkwUlkuVa99MrvKdVWo//yz83qex8g= c=1 sm=0 a=Py4kDrXLE7IA:10 a=fF8sIQlIHz0A:10 a=nDghuxUhq_wA:10 a=8nJEP1OIZ-IA:10 a=2Aa9k38lAAAA:8 a=4nz5CTYPk0NPMhn6O6EA:9 a=wPNLvfGTeEIA:10 a=4FNkeMFYW91jQMy9:21 a=UZlyAv-mPOZPeol4:21 a=HpAAvcLHHh0Zw7uRqdWCyQ==:117 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list 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: 46 NNTP-Posting-Host: 82.94.164.166 X-Trace: 1307611213 news.xs4all.nl 49183 [::ffff:82.94.164.166]:36395 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7282 On 09/06/2011 09:31, Ganapathy Subramanium wrote: > Hi Guru's, > > I'm working on a solution to find the prime factor of the number > This part of the code works.. http://www.pastie.org/2041584 > > When the number gets bigger, the range cannot iterate through bigger > number and it does not work. > > When I googled , I came across creating our own range function to > solve this. I was just wondering if there was a better algorithm to > get the prime numbers / prime factors of a long number? > > > Any inputs is highly appreciated. > > If I was attempting this problem, I would pre-compute a file of prime numbers, in increasing order (probably use the Sieve of Erastothenes approach). You need a list of primes from 2 to the square root of the largest num you will have to process. With that, you simply work through the prime numbers, Divide num by this prime. If no remainder, replace num with num // prime (so you divide by the same prime again). else step on to next prime without changing num Stop when num becomes 1. e.g. 50 divides by 2 so factors are (2) and 25 into next iteration with 3 25 which won't divide by 3, so factors remain (2) and 25 goes into next iteration with 5 25 // 5 is 5 so factors become (2,5) and 5 into next iteration with 5 5 // 5 is 1 so factors are (2,5,5) and computation complete. Ian