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

[Mel]

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.