Any Better logic for this problem..

[geremy condra]

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