On Thu, Jun 9, 2011 at 6:10 PM, Dan Stromberg <drsali...@gmail.com> wrote: > > On Thu, Jun 9, 2011 at 10:55 AM, geremy condra <debat...@gmail.com> wrote: >> >> 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 > > You Might be able to benefit from a primality test like Miller-Rabin, at > least if your numbers can be really large. It can answer with "this number > is definitely composite" or "this number is probably prime". For quite > large numbers, it might speed things up. For smaller numbers, trial > division is faster. > > I have a Python Miller-Rabin module at: > > http://stromberg.dnsalias.org/svn/big-prime/trunk/
Here's a non-gmpy randomized MR implementation: import random def miller_rabin(n, confidence=20): t, s, d = n-1, 0, 0 while not t % 2: t = t >> 1 s += 1 t, d = n-1, t for i in range(confidence): a = random.randrange(2, n) x = pow(a, d, n) if x == 1: continue if x == t: continue for r in range(1, s): x = pow(x, 2, n) if x == t: break if x == 1: return False else: return False return True -- http://mail.python.org/mailman/listinfo/python-list