2520 is a number divisible by all integers from 1 to 10 and is the smallest of such numbers. Then, what is the smallest positive number among the numbers divisible by all integers from 1 to 20?
Python
MAX = 20
seq = range(1, MAX+1)
def compute_prime_factors(x):
prime_factors = {}
i = 2
while x > 1:
if x % i == 0:
if(not prime_factors.has_key(i)):
prime_factors[i] = 0
prime_factors[i] += 1
x = x / i
else:
i += 1
return prime_factors
prime_factors = [compute_prime_factors(i) for i in seq]
result_dic = {}
for dic in prime_factors:
for key in dic.keys():
if(result_dic.has_key(key)):
result_dic[key] = max(result_dic[key], dic[key])
else:
result_dic[key] = dic[key]
factors = [key ** result_dic[key] for key in result_dic.keys()]
result = reduce(lambda x,y: x * y, factors)
print result
print result == 232792560
print prime_factors
print result_dic
print factors
result
232792560
True
[{}, {2: 1}, {3: 1}, {2: 2}, {5: 1}, {2: 1, 3: 1}, {7: 1}, {2: 3}, {3: 2}, {2: 1, 5: 1}, {11: 1}, {2: 2, 3: 1}, {13: 1}, {2: 1, 7: 1}, {3: 1, 5: 1}, {2: 4}, {17: 1}, {2: 1, 3: 2}, {19: 1}, {2: 2, 5: 1}]
{2: 4, 3: 2, 5: 1, 7: 1, 11: 1, 13: 1, 17: 1, 19: 1}
[16, 9, 5, 7, 11, 13, 17, 19]
Recommended Posts