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

[John Salerno]

On Jun 21, 10:02 pm, Mel <mwil... at 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.