Any Better logic for this problem..

[Dan Stromberg]

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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110609/cd2c2816/attachment-0001.html>