Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #8126

Re: How can I speed up a script that iterates over a large range (600 billion)?

Show all headers | View raw

On 21/06/2011 20:48, John Salerno wrote:
> I'm working on the Project Euler exercises and I'm stumped on problem
> 3:
>
> "What is the largest prime factor of the number 600851475143 ?"
>
> Now, I've actually written functions to get a list of the factors of
> any given number, and then another function to get the prime numbers
> from that list. It works fine with small numbers, but when I try to
> feed my get_factors function with the above number (600 billion),
> naturally it takes forever! But according to the Project Euler
> website:
>
> "I've written my program but should it take days to get to the answer?
>
> Absolutely not! Each problem has been designed according to a "one-
> minute rule", which means that although it may take several hours to
> design a successful algorithm with more difficult problems, an
> efficient implementation will allow a solution to be obtained on a
> modestly powered computer in less than one minute."
>
> But it definitely takes more than a minute, and I still haven't gotten
> it to end yet without just canceling it myself.
>
[snip]
A non-prime is the product of a prime and another number which may or
may not be a prime. Look for the smallest prime and repeat.

On a modern PC, if it takes more than, say, a second for the given
number, you're doing it wrong. :-)

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

Thread

How can I speed up a script that iterates over a large range (600 billion)? John Salerno <johnjsal@gmail.com> - 2011-06-21 12:48 -0700
  Re: How can I speed up a script that iterates over a large range (600 billion)? Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-21 14:02 -0600
  Re: How can I speed up a script that iterates over a large range (600 billion)? Irmen de Jong <irmen@-NOSPAM-xs4all.nl> - 2011-06-21 22:10 +0200
    sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? Irmen de Jong <irmen@-NOSPAM-xs4all.nl> - 2011-06-21 22:22 +0200
      Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? John Salerno <johnjsal@gmail.com> - 2011-06-21 14:09 -0700
        Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? Irmen de Jong <irmen.NOSPAM@xs4all.nl> - 2011-06-21 23:39 +0200
        Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-21 15:41 -0600
          Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? John Salerno <johnjsal@gmail.com> - 2011-06-21 14:48 -0700
        Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? Vlastimil Brom <vlastimil.brom@gmail.com> - 2011-06-21 23:33 +0200
        Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? Paul Rubin <no.email@nospam.invalid> - 2011-06-21 17:05 -0700
          Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? John Salerno <johnjsal@gmail.com> - 2011-06-21 18:21 -0700
            Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? Paul Rubin <no.email@nospam.invalid> - 2011-06-21 19:09 -0700
              Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? John Salerno <johnjsal@gmail.com> - 2011-06-21 20:02 -0700
                Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? Irmen de Jong <irmen.NOSPAM@xs4all.nl> - 2011-06-22 19:46 +0200
            Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? MRAB <python@mrabarnett.plus.com> - 2011-06-22 03:10 +0100
            Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? Mel <mwilson@the-wire.com> - 2011-06-21 23:02 -0400
              Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)? John Salerno <johnjsal@gmail.com> - 2011-06-21 20:41 -0700
  Re: How can I speed up a script that iterates over a large range (600 billion)? Mel <mwilson@the-wire.com> - 2011-06-21 16:19 -0400
    Re: How can I speed up a script that iterates over a large range (600 billion)? Tim Roberts <timr@probo.com> - 2011-06-22 23:21 -0700
  Re: How can I speed up a script that iterates over a large range (600 billion)? MRAB <python@mrabarnett.plus.com> - 2011-06-21 21:26 +0100
  Re: How can I speed up a script that iterates over a large range (600 billion)? Terry Reedy <tjreedy@udel.edu> - 2011-06-21 19:30 -0400
    Re: How can I speed up a script that iterates over a large range (600 billion)? Paul Rubin <no.email@nospam.invalid> - 2011-06-21 17:00 -0700
      Re: How can I speed up a script that iterates over a large range (600 billion)? Terry Reedy <tjreedy@udel.edu> - 2011-06-22 00:18 -0400
        Re: How can I speed up a script that iterates over a large range (600 billion)? Paul Rubin <no.email@nospam.invalid> - 2011-06-21 22:32 -0700
          Re: How can I speed up a script that iterates over a large range (600 billion)? Terry Reedy <tjreedy@udel.edu> - 2011-06-22 18:46 -0400
  Re: How can I speed up a script that iterates over a large range (600 billion)? Benjamin Kaplan <benjamin.kaplan@case.edu> - 2011-06-21 20:07 -0700
  Re: How can I speed up a script that iterates over a large range (600 billion)? Chris Torek <nospam@torek.net> - 2011-06-22 05:58 +0000
    Re: How can I speed up a script that iterates over a large range (600 billion)? Paul Rubin <no.email@nospam.invalid> - 2011-06-21 23:23 -0700
      Re: How can I speed up a script that iterates over a large range (600 billion)? Slaunger <slaunger@gmail.com> - 2011-06-23 02:52 -0700
    Re: How can I speed up a script that iterates over a large range (600 billion)? Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-22 01:16 -0600
    Re: How can I speed up a script that iterates over a large range (600 billion)? Anny Mous <b1540457@tyldd.com> - 2011-06-22 22:01 +1000
      Re: How can I speed up a script that iterates over a large range (600 billion)? Chris Angelico <rosuav@gmail.com> - 2011-06-22 22:28 +1000
      Re: How can I speed up a script that iterates over a large range (600 billion)? Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-22 09:52 -0600
    Re: How can I speed up a script that iterates over a large range (600 billion)? MRAB <python@mrabarnett.plus.com> - 2011-06-22 16:33 +0100

csiph-web