Any Better logic for this problem..

[geremy condra]

On Thu, Jun 9, 2011 at 6:10 PM, Dan Stromberg <drsalists at gmail.com> wrote:
>
> On Thu, Jun 9, 2011 at 10:55 AM, geremy condra <debatem1 at gmail.com> wrote:
>>
>> On Thu, Jun 9, 2011 at 4:38 AM, Dave Angel <davea at 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.subramanium at 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