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.

.

Relevant Pages