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

Groups > comp.lang.python > #8124

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

Followups directed to: comp.lang.python

Show key headers only | View raw

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 ?"
[ ... ]
> Here is what I have so far. Initially the get_factors function just
> iterated over the entire range(2, n + 1), but since a number can't
> have a factor greater than half of itself, I tried to shorten the
> range by doing range(2, n //2), but that still leaves 300 billion
> numbers to go through.
> 
> def get_factors(number):
>     factors = [number]
> 
>     for n in range(2, number // 2):
>         if number % n == 0:
>             factors.append(n)
> 
>     return factors
> 
> 
> def get_primes(number_list):
>     primes = number_list[:]
> 
>     for n in number_list:
>         for x in range(2, n):
>             if n % x == 0:
>                 primes.remove(n)
>                 break
> 
>     return primes
> 
> 
> print(max(get_primes(get_factors(600851475143))))
> 
> 
> Also, I want to make it clear that I DO NOT WANT THE ANSWER. I really
> want to solve this myself, but the reason I'm asking about it is to
> see if there really is some way to change this code so that it can get
> an answer in less than one minute, as the website says should be
> possible. A hint about what I need to do would be nice, but not an
> answer. I just don't see any way to get the factors without iterating
> over the entire range of values, though.

It certainly can be done faster.  I ran it against the factor finder that I 
wrote, and it popped up the answer

mwilson@tecumseth:~$ bin/factors.py 600851475143
71 839 1471 ...

before I could glance at my watch.  factors.py works, as does yours, by 
testing for small factors first, but it divides them out as it goes, so it 
tends to do its work on smallish numbers.  And since the smallest factors 
are taken out as soon as possible, they have to be the prime ones.

	Good hunting,		Mel.

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