Finding greatest prime factor, was Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

Date	2011-06-22 08:59 +1000
Subject	Finding greatest prime factor, was Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?
From	Chris Angelico <rosuav@gmail.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.248.1308697176.1164.python-list@python.org> (permalink)

Show all headers | View raw

On Wed, Jun 22, 2011 at 7:48 AM, John Salerno <johnjsal@gmail.com> wrote:
> Thanks for the all the advice everyone. Now I'm on to problem #4, and
> I'm stumped again, but that's what's fun! :)

So now that you've solved it, I'd like to see some fast one-liners to
do the job. (Since Python cares about whitespace, it might not
_technically_ fit on one line, but in the spirit of one-liners, try to
keep it short.)

Here's what I did in Pike, very quickly:
exec 600851475143; for (int i=2;i<ret;++i) while (ret%i==0) ret/=i

Porting it to Python:
ret,i=600851475143,2
while i<ret:
  while not ret%i:
    ret//=i

Bring on your simpler solutions!

ChrisA

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Finding greatest prime factor, was Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? Chris Angelico <rosuav@gmail.com> - 2011-06-22 08:59 +1000

csiph-web