Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!selfless.tophat.at!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=HRbP+JUBYmfXH7jByubSFxoafUk1vcnnKoM/g9Qm1hVulsYIY6OALshKnmDJiJbFaE DkCC+dCXppE2BI0Xdp1nDrDLTIUbDBYK89oo/gon6KEuCY5uOHHK+aeEh6iuuz291+ol g4T89RXSVqXMKSxpD7Ln41pbGJ6kBW41c3zwg=
MIME-Version: 1.0
In-Reply-To: <BANLkTin2BEBJMuTvDWr5w0b_BX3zcFOa=g@mail.gmail.com>
References: <BANLkTinWq5pjX2+0OVRvm1Xs7ESmYf0qcw@mail.gmail.com> <BANLkTimicVsm7EGMsVu0bXRsa7714MKpwA@mail.gmail.com> <4DF0B0BE.3020907@ieee.org> <BANLkTinv6kB5e0T+r7XmTiUaV3sGH0CAYQ@mail.gmail.com> <BANLkTin2BEBJMuTvDWr5w0b_BX3zcFOa=g@mail.gmail.com>
Date: Fri, 10 Jun 2011 01:10:28 -0700
Subject: Re: Any Better logic for this problem..
From: geremy condra <debatem1@gmail.com>
To: Dan Stromberg <drsalists@gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Cc: python-list@python.org, sganapathy.subramanium@gmail.com, davea@ieee.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.80.1307693432.11593.python-list@python.org>
Lines: 116
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7363

On Thu, Jun 9, 2011 at 6:10 PM, Dan Stromberg <drsalists@gmail.com> wrote:
>
> On Thu, Jun 9, 2011 at 10:55 AM, geremy condra <debatem1@gmail.com> wrote=
:
>>
>> On Thu, Jun 9, 2011 at 4:38 AM, Dave Angel <davea@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@gmail.com> =A0wrote:
>> >>>
>> >>> 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 th=
e
>> >>> 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. =A0Do you really have a need to factor number=
s
>> > over 2
>> > billion? =A0Repeatedly? =A0In multiple runs of the program? =A0Do you =
have
>> > weeks
>> > of computer time to spend or just hours? =A0Are you really interested =
in
>> > the
>> > factors, or just whether or not a particular large number is prime
>> > (=3D=3Dhas
>> > anyfactors) ? =A0If this is a homework assignment, what's the exact
>> > assignment? =A0Are you permitted to use other libraries, or other
>> > languages?
>> > =A0Are you permitted to use language features you haven't encountered =
yet
>> > in
>> > class?
>>
>> My solution:
>>
>> def factors(x):
>> =A0 status, output =3D subprocess.getstatusoutput('factor %d' % x)
>> =A0 if not status:
>> =A0 =A0 =A0 =A0return [int(i) for i in output.split()[1:]]
>> =A0 else:
>> =A0 =A0 =A0 =A0print(output)
>>
>> Works pretty well.
>>
>> <snip>
>>
>> > So you should probably turn the problem around. =A0Design a function t=
hat
>> > calculates the nth prime, but that caches the work it's already done (=
on
>> > disk if appropriate, but in a list if not). =A0In the loop that's find=
ing
>> > 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.=A0 It can answer with "this nu=
mber
> is definitely composite" or "this number is probably prime".=A0 For quite
> large numbers, it might speed things up.=A0 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=3D20):
	t, s, d =3D n-1, 0, 0
	while not t % 2:
		t =3D t >> 1
		s +=3D 1
	t, d =3D n-1, t

	for i in range(confidence):
		a =3D random.randrange(2, n)
		x =3D pow(a, d, n)
		if x =3D=3D 1: continue
		if x =3D=3D t: continue
		for r in range(1, s):
			x =3D pow(x, 2, n)
			if x =3D=3D t: break
			if x =3D=3D 1: return False
		else: return False
	return True