On Thu, Jun 9, 2011 at 4:38 AM, Dave Angel <da...@ieee.org> wrote: > On 01/-10/-28163 02:59 PM, Chris Rebert wrote: >> >> On Thu, Jun 9, 2011 at 1:31 AM, Ganapathy Subramanium >> <sganapathy.subraman...@gmail.com> 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. >> > > Others have pointed out various inefficiencies. But I wanted to start by > asking what this is for. Do you really have a need to factor numbers over 2 > billion? Repeatedly? In multiple runs of the program? Do you have weeks > of computer time to spend or just hours? Are you really interested in the > factors, or just whether or not a particular large number is prime (==has > anyfactors) ? If this is a homework assignment, what's the exact > assignment? Are you permitted to use other libraries, or other languages? > Are you permitted to use language features you haven't encountered yet in > class?
My solution: def factors(x): status, output = subprocess.getstatusoutput('factor %d' % x) if not status: return [int(i) for i in output.split()[1:]] else: print(output) Works pretty well. <snip> > So you should probably turn the problem around. Design a function that > calculates the nth prime, but that caches the work it's already done (on > disk if appropriate, but in a list if not). In the loop that's finding the > factors, simply call the first function each time, and each time you find a > factor, divide num by that so you're dealing with a smaller number. Just use a precomputed table to do your trial division. There's a list of the first fifty million primes on prime pages- if you aren't dealing with specially constructed values (ie, RSA moduli) and haven't found a factor by the end of the first ten thousand or so you probably need to do a primality check before moving on to trying to factor it. Geremy Condra -- http://mail.python.org/mailman/listinfo/python-list