Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!news.stack.nl!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=U/aWL7LvYMfXDLxkEUxs9WEcEubJ9JtkQ+ksLMVuoI6XFAKaZAY01sRQaNiQxOsSDQ FQmjv3HJ4tA1X2ZQ+ZhIqHTH+nRhfEBLnWk/orlyC3NWwxtvoNQtwYBy5dNNH0G8ybg6 xuJmezHYA/qjszvYO4IvvmTCK1R0pf0hXe52E=
MIME-Version: 1.0
In-Reply-To: <4DF0B0BE.3020907@ieee.org>
References: <BANLkTinWq5pjX2+0OVRvm1Xs7ESmYf0qcw@mail.gmail.com> <BANLkTimicVsm7EGMsVu0bXRsa7714MKpwA@mail.gmail.com> <4DF0B0BE.3020907@ieee.org>
Date: Thu, 9 Jun 2011 10:55:04 -0700
Subject: Re: Any Better logic for this problem..
From: geremy condra <debatem1@gmail.com>
To: davea@ieee.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Cc: python-list@python.org, sganapathy.subramanium@gmail.com
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.57.1307642108.11593.python-list@python.org>
Lines: 65
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7311

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 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. =A0Do you really have a need to factor numbers o=
ver 2
> billion? =A0Repeatedly? =A0In multiple runs of the program? =A0Do you hav=
e 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 languag=
es?
> =A0Are you permitted to use language features you haven't encountered yet=
 in
> class?

My solution:

def factors(x):
   status, output =3D 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. =A0Design 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). =A0In 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