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

Groups > comp.lang.python > #8119 > unrolled thread

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

Back to article view | Back to comp.lang.python

Contents

  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

Page 1 of 2  [1] 2  Next page →

#8119 — How can I speed up a script that iterates over a large range (600 billion)?

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.

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.

Thanks!

[toc] | [next] | [standalone]

#8120

On Tue, Jun 21, 2011 at 1:48 PM, John Salerno <johnjsal@gmail.com> wrote:
> 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.

Without giving you the answer, I will note that the range can be
further reduced by quite a lot (I'm talking orders of magnitude, not
just by half).

> 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

Also, primality testing and factorization are very similar problems,
and the same range optimization could be applied here as well.

Cheers,
Ian

[toc] | [prev] | [next] | [standalone]

#8122

On 21-06-11 21: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!

You need a better algorithm to calculate primes, and iterate over primes 
instead of over the full (half, or even better, sqrt(n)) range of 
possible values. You also should optimize the stop condition, once you 
find that the number can no longer be divided by larger primes you can 
stop the loop.

For instance to get the prime factors of the number 1000 you'd iterate
over the prime numbers 2,3,5 and conclude that

1000=2*2*2*5*5*5, so 5 would be the largest prime factor.

No need to try larger primes than 5, let alone go through 1..sqrt(1000).

The Sieve of Eratosthenes is a well known algorithm to calculate primes 
with reasonable efficiency.

Irmen

[toc] | [prev] | [next] | [standalone]

#8125 — sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

On 21-06-11 22:10, Irmen de Jong wrote:
[stuff]

I didn't read the last paragraph of John's message until just now, and 
now realize that what I wrote is likely way too much information for 
what he asked.
I'm sorry. Next time I'll read everything until and including the last 
full stop.

Irmen

[toc] | [prev] | [next] | [standalone]

#8130 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

On Jun 21, 3:22 pm, Irmen de Jong <ir...@-NOSPAM-xs4all.nl> wrote:
> On 21-06-11 22:10, Irmen de Jong wrote:
> [stuff]
>
> I didn't read the last paragraph of John's message until just now, and
> now realize that what I wrote is likely way too much information for
> what he asked.
> I'm sorry. Next time I'll read everything until and including the last
> full stop.
>
> Irmen

Don't worry, I was still unclear about what to do after reading all
the responses, even yours! But one thing that made me feel better was
that I wasn't having a Python problem as much as a *math* problem. I
changed my get_factors function to only go as far as the square root
of the number in question, and that yielded an answer immediately. :)

However, even after reading the Wikipedia page about prime numbers and
trial division, I'm still a little unclear as to why the square root
of the number is the upper bound of the range you need to check.

[toc] | [prev] | [next] | [standalone]

#8134 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

On 21-6-2011 23:09, John Salerno wrote:
> On Jun 21, 3:22 pm, Irmen de Jong <ir...@-NOSPAM-xs4all.nl> wrote:
>> On 21-06-11 22:10, Irmen de Jong wrote:
>> [stuff]
>>
>> I didn't read the last paragraph of John's message until just now, and
>> now realize that what I wrote is likely way too much information for
>> what he asked.
>> I'm sorry. Next time I'll read everything until and including the last
>> full stop.
>>
>> Irmen
> 
> Don't worry, I was still unclear about what to do after reading all
> the responses, even yours! But one thing that made me feel better was
> that I wasn't having a Python problem as much as a *math* problem. I
> changed my get_factors function to only go as far as the square root
> of the number in question, and that yielded an answer immediately. :)

Ok, cool :)


> However, even after reading the Wikipedia page about prime numbers and
> trial division, I'm still a little unclear as to why the square root
> of the number is the upper bound of the range you need to check.

If there is an exact divisor d >= √n, then the quotient n/d is also a divisor of n, and
that quotient is <= √n. So if we don't find such a quotient before reaching √n, it's not
useful to search for d > √n (because no divisors would be found).

Irmen

[toc] | [prev] | [next] | [standalone]

#8135 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

On Tue, Jun 21, 2011 at 3:09 PM, John Salerno <johnjsal@gmail.com> wrote:
> Don't worry, I was still unclear about what to do after reading all
> the responses, even yours! But one thing that made me feel better was
> that I wasn't having a Python problem as much as a *math* problem. I
> changed my get_factors function to only go as far as the square root
> of the number in question, and that yielded an answer immediately. :)
>
> However, even after reading the Wikipedia page about prime numbers and
> trial division, I'm still a little unclear as to why the square root
> of the number is the upper bound of the range you need to check.

Careful, note that the greatest prime factor may actually be greater
than the square root.  It's just that it's possible to find it without
iterating past the square root.  This is because for each p that is a
factor of n, q is also a factor of n, where p * q = n.  If p >
sqrt(n), then q < sqrt(n).  Therefore you can find p by finding q and
dividing n / q.

[toc] | [prev] | [next] | [standalone]

#8137 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

On Jun 21, 4:41 pm, Ian Kelly <ian.g.ke...@gmail.com> wrote:
> On Tue, Jun 21, 2011 at 3:09 PM, John Salerno <johnj...@gmail.com> wrote:
> > Don't worry, I was still unclear about what to do after reading all
> > the responses, even yours! But one thing that made me feel better was
> > that I wasn't having a Python problem as much as a *math* problem. I
> > changed my get_factors function to only go as far as the square root
> > of the number in question, and that yielded an answer immediately. :)
>
> > However, even after reading the Wikipedia page about prime numbers and
> > trial division, I'm still a little unclear as to why the square root
> > of the number is the upper bound of the range you need to check.
>
> Careful, note that the greatest prime factor may actually be greater
> than the square root.  It's just that it's possible to find it without
> iterating past the square root.  This is because for each p that is a
> factor of n, q is also a factor of n, where p * q = n.  If p >
> sqrt(n), then q < sqrt(n).  Therefore you can find p by finding q and
> dividing n / q.

Oh! Now it makes sense! That first sentence helped to put it into
perspective, too. The Wikipedia page says more or less the same thing,
but this paragraph just made more sense to me. :)

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! :)

[toc] | [prev] | [next] | [standalone]

#8146 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

2011/6/21 John Salerno <johnjsal@gmail.com>:
> However, even after reading the Wikipedia page about prime numbers and
> trial division, I'm still a little unclear as to why the square root
> of the number is the upper bound of the range you need to check.
> --

There are likely be some more elaborated proofs, but it seems
sufficiently evident, that with the factors being the square root you
get some kind of "middle position"; with other factors (e.g. two for
simplicity), one of them could be greater, while the another has to be
smaller; this smaller one would have been discovered already, while
searching continuously until the square root of the given number.

vbr

[toc] | [prev] | [next] | [standalone]

#8148 — 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> writes:
> However, even after reading the Wikipedia page about prime numbers and
> trial division, I'm still a little unclear as to why the square root
> of the number is the upper bound of the range you need to check.

Suppose p is the smallest divisor of n, and p > sqrt(n).
("Divisor" here means p=1 doesn't count).

p being a divisor of n means there is some q such that n = pq.
That means q = n / p.

If p > sqrt(n) that means that q must be < sqrt(n).  But that
contradicts the claim that p is the smallest divisor.

So we know that if there is a divisor at all, it must be <= sqrt(n)
and if we don't find one by then, n must be prime.

[toc] | [prev] | [next] | [standalone]

#8162 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

::sigh:: Well, I'm stuck again and it has to do with my get_factors
function again, I think. Even with the slight optimization, it's
taking forever on 20! (factorial, not excitement)  :) It's frustrating
because I have the Python right, but I'm getting stuck on the math.

The problem:

"What is the smallest positive number that is evenly divisible by all
of the numbers from 1 to 20?"



Here's the function (it's in the problem3.py file, hence the import
below):

import math

def get_factors(number):
    factors = []

    for n in range(2, int(math.sqrt(number))):
        if number % n == 0:
            factors.append(n)
            factors.append(number // n)

    return factors

And here's my new script for the new exercise:

import math
from problem3 import get_factors

max_num = 20
n = math.factorial(max_num)
factors = get_factors(n)
div_all = []

for x in factors:
    for y in range(2, max_num+1):
        if x % y != 0:
            break
        elif y == max_num:
            div_all.append(x)

print(min(div_all))

It could easily be that I'm simply approaching it all wrong. I just
thought that maybe using the factorial of the highest number in the
range (in this case, 20) would be an easy way of finding which numbers
to test.

[toc] | [prev] | [next] | [standalone]

#8164 — 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> writes:
> It's frustrating because I have the Python right, but I'm getting
> stuck on the math....
> "What is the smallest positive number that is evenly divisible by all
> of the numbers from 1 to 20?"

The answer is lcm [1,2,3, ... 20].  You can figure out how to implement
lcm.

The Euler problems are not really programming exercises.  They are
exercises in math and algorithms.  Quite a lot of them involve thinking
clever and fast ways to do stuff that would be trivial (but too slow) by
brute force.  In general, once you figure out the right algorithm,
writing the code is easy.  But you have to be fairly mathematically
attuned, to have any chance of spotting the algorithm.

If you want programming exercises that are less mathematical, there are
some nice ones at rubyquiz.com.  They are intended for Ruby but of
course you can solve them in Python.

[toc] | [prev] | [next] | [standalone]

#8171 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

On Jun 21, 9:09 pm, Paul Rubin <no.em...@nospam.invalid> wrote:
> John Salerno <johnj...@gmail.com> writes:
> > It's frustrating because I have the Python right, but I'm getting
> > stuck on the math....
> > "What is the smallest positive number that is evenly divisible by all
> > of the numbers from 1 to 20?"
>
> The answer is lcm [1,2,3, ... 20].  You can figure out how to implement
> lcm.
>
> The Euler problems are not really programming exercises.  They are
> exercises in math and algorithms.  Quite a lot of them involve thinking
> clever and fast ways to do stuff that would be trivial (but too slow) by
> brute force.  In general, once you figure out the right algorithm,
> writing the code is easy.  But you have to be fairly mathematically
> attuned, to have any chance of spotting the algorithm.
>
> If you want programming exercises that are less mathematical, there are
> some nice ones at rubyquiz.com.  They are intended for Ruby but of
> course you can solve them in Python.

Thanks. So far they are helping me with Python too, but definitely not
as much as more general exercises would, I'm sure. The part about
writing the code is fun, but once that's done, I seem to end up stuck
with an inefficient implementation because I don't know the math
tricks behind the problem.

I'll check out rubyquiz.com. I've been searching for some Python
exercises to do but haven't found too many sites with them, at least
not in such a nice and organized way as Project Euler.

[toc] | [prev] | [next] | [standalone]

#8235 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

On 22-6-2011 5:02, John Salerno wrote:

> Thanks. So far they are helping me with Python too, but definitely not
> as much as more general exercises would, I'm sure. The part about
> writing the code is fun, but once that's done, I seem to end up stuck
> with an inefficient implementation because I don't know the math
> tricks behind the problem.
> 
> I'll check out rubyquiz.com. I've been searching for some Python
> exercises to do but haven't found too many sites with them, at least
> not in such a nice and organized way as Project Euler.

There's also SPOJ; http://www.spoj.pl/problems/classical/
It has tons of problems, many math related, but also silly ones like this:
https://www.spoj.pl/problems/JAVAC/
and perhaps even useful ones like this:
https://www.spoj.pl/problems/ONP/

Irmen

[toc] | [prev] | [next] | [standalone]

#8165 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

On 22/06/2011 02:21, John Salerno wrote:
> ::sigh:: Well, I'm stuck again and it has to do with my get_factors
> function again, I think. Even with the slight optimization, it's
> taking forever on 20! (factorial, not excitement)  :) It's frustrating
> because I have the Python right, but I'm getting stuck on the math.
>
> The problem:
>
> "What is the smallest positive number that is evenly divisible by all
> of the numbers from 1 to 20?"
>
You don't need factorials, just remember that each of the numbers can
be expressed as the product of a multiset of prime factors.

[toc] | [prev] | [next] | [standalone]

#8169 — 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 wrote:

> ::sigh:: Well, I'm stuck again and it has to do with my get_factors
> function again, I think. Even with the slight optimization, it's
> taking forever on 20! (factorial, not excitement)  :) It's frustrating
> because I have the Python right, but I'm getting stuck on the math.
> 
> The problem:
> 
> "What is the smallest positive number that is evenly divisible by all
> of the numbers from 1 to 20?"
> 
> 
> 
> Here's the function (it's in the problem3.py file, hence the import
> below):
> 
> import math
> 
> def get_factors(number):
>     factors = []
> 
>     for n in range(2, int(math.sqrt(number))):
>         if number % n == 0:
>             factors.append(n)
>             factors.append(number // n)
> 
>     return factors
> 
> And here's my new script for the new exercise:
> 
> import math
> from problem3 import get_factors
> 
> max_num = 20
> n = math.factorial(max_num)
> factors = get_factors(n)
> div_all = []
> 
> for x in factors:
>     for y in range(2, max_num+1):
>         if x % y != 0:
>             break
>         elif y == max_num:
>             div_all.append(x)
> 
> print(min(div_all))
> 
> It could easily be that I'm simply approaching it all wrong. I just
> thought that maybe using the factorial of the highest number in the
> range (in this case, 20) would be an easy way of finding which numbers
> to test.

These are almost "trick questions" in a way, because of the math behind 
them.  If the question were "What is the tallest high-school student in 
Scranton, PA?" then searching a population for the property would be the 
only way to go.  BUT you can also build up the answer knowing the 
factorization of all the numbers up to 20.

	Mel.

[toc] | [prev] | [next] | [standalone]

#8177 — Re: sorry, possibly too much info. was: Re: How can I speed up a script that iterates over a large range (600 billion)?

On Jun 21, 10:02 pm, Mel <mwil...@the-wire.com> wrote:
> John Salerno wrote:
> > ::sigh:: Well, I'm stuck again and it has to do with my get_factors
> > function again, I think. Even with the slight optimization, it's
> > taking forever on 20! (factorial, not excitement)  :) It's frustrating
> > because I have the Python right, but I'm getting stuck on the math.
>
> > The problem:
>
> > "What is the smallest positive number that is evenly divisible by all
> > of the numbers from 1 to 20?"
>
> > Here's the function (it's in the problem3.py file, hence the import
> > below):
>
> > import math
>
> > def get_factors(number):
> >     factors = []
>
> >     for n in range(2, int(math.sqrt(number))):
> >         if number % n == 0:
> >             factors.append(n)
> >             factors.append(number // n)
>
> >     return factors
>
> > And here's my new script for the new exercise:
>
> > import math
> > from problem3 import get_factors
>
> > max_num = 20
> > n = math.factorial(max_num)
> > factors = get_factors(n)
> > div_all = []
>
> > for x in factors:
> >     for y in range(2, max_num+1):
> >         if x % y != 0:
> >             break
> >         elif y == max_num:
> >             div_all.append(x)
>
> > print(min(div_all))
>
> > It could easily be that I'm simply approaching it all wrong. I just
> > thought that maybe using the factorial of the highest number in the
> > range (in this case, 20) would be an easy way of finding which numbers
> > to test.
>
> These are almost "trick questions" in a way, because of the math behind
> them.  If the question were "What is the tallest high-school student in
> Scranton, PA?" then searching a population for the property would be the
> only way to go.  BUT you can also build up the answer knowing the
> factorization of all the numbers up to 20.
>
>         Mel.

I think you're right. I just read the next problem and it is similar
in style, i.e. the example solution involves a small set of numbers
which I can write a script for and it would execute within a second,
but when I expand the script to include the larger set of numbers for
the problem, it then takes ages to execute, making me feel like the
trick isn't to figure out the right code, but the right math.

[toc] | [prev] | [next] | [standalone]

#8124

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.

[toc] | [prev] | [next] | [standalone]

#8269

Mel <mwilson@the-wire.com> wrote:
>
>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.

That's a great hint, and I'm not sure it would have occurred to me on my
own.  Using your hint, I was able to write a 16-line script that also
produced a result instantaneously.  Very satisfying.

I'm going to save that one...
-- 
Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

[toc] | [prev] | [next] | [standalone]

#8126

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. :-)

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web