# Problem 5: smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

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

## Understanding the problem

The approach will be the following:

• Create a list of all the factors of the numbers from 1 to 20
• Obtain all the different factors. Get the equal factors with the greatest exponent
• Multiply the factors: this is the solution

Functions for obtaining all the factors of a number

``````

In [57]:

def factor(N):
for i in range(2,N):
if (N % i == 0):
return i
return 0

def decompose(N):
f = factor(N)
lf = []
while f > 0:
lf.append(f)
N = N / f
#print("Factor: {}, Rest: {}".format(f, N)) #-- Debuging
f = factor(N)
lf.append(N)

#-- Create a dictionary with the factors and exponents
d = {}
for f in lf:
try:
d[f] += 1
except:
d[f] = 1

return d

``````

Checking the function

``````

In [58]:

for i in range(2,21):
print("{}: {}".format(i, decompose(i)))

``````
``````

2: {2: 1}
3: {3: 1}
4: {2: 2}
5: {5: 1}
6: {2: 1, 3: 1}
7: {7: 1}
8: {2: 3}
9: {3: 2}
10: {2: 1, 5: 1}
11: {11: 1}
12: {2: 2, 3: 1}
13: {13: 1}
14: {2: 1, 7: 1}
15: {3: 1, 5: 1}
16: {2: 4}
17: {17: 1}
18: {2: 1, 3: 2}
19: {19: 1}
20: {2: 2, 5: 1}

``````

Now all the factors should be included in a new dictionary following the criteria of including the ones with the maximum exponent or factors that are not already there

``````

In [76]:

df = {}
for i in range(2,21):
d = decompose(i)
for f in d.keys():
try:
df[f] = max(df[f], d[f])
except:
df[f] = 1

``````

Finally, al the factors should be multiplied between them to obtaing the solution

``````

In [77]:

n = 1
for f in df.keys():
n = n * (f ** df[f])

``````
``````

In [78]:

print("The solution is: {}".format(n))

``````
``````

The solution is: 232792560

``````
``````

In [ ]:

``````