# Project Euler Problem5

2013-12-12 来源： tianxiaozz 发布在  https://www.cnblogs.com/tianxiaozz/p/3471606.html

## Smallest multiple

### Problem 5

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?

From problem 3, we get a list of prime factors of a number . Base on this, we get the prime factors for number from 1 to 20.

And we merge them together. The rule is, we get the largest times for each prime factor. Then we mutiply them.

The python code is as follows:

```def getPrimeFactorDic(data):
dic = {}
i = 2
while i <= math.sqrt(data):
#while i <= data/2:
if data%i == 0 :
putIntoDic(dic, i)
data = (int)(data/i)
#i = 2
else:
i += 1
putIntoDic(dic, data)
return dic

def putIntoDic(dic, key):
if key in dic:
dic[key] += 1
else:
dic[key] = 1

def mergeIntoDic(dic, key, value):
if key in dic:
if value > dic[key]:
dic[key] = value
else:
dic[key] = value

print(getPrimeFactorDic(10))
myDic = {}
for i in range(1, 21):
tempDic = getPrimeFactorDic(i)
for key in tempDic.keys():
mergeIntoDic(myDic, key, tempDic[key])
print(myDic)

mathProduct = 1
for key in myDic.keys():
mathProduct *= pow(key, myDic[key])
print(mathProduct)
```