欧拉工程第五解

| Comments

第五解:

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 number that is evenly divisible by all of the numbers from 1 to 20?

解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#为简洁明了,此处不作校验
def GetGreatestCommonDivisor(min,max):
    '''辗转相除法求最大公约数'''
    while min > 0:
        tmp = min
        min = max % min
        max = tmp
    return max

def GetLeastCommonMultiple(a,b):
    if a > b:
        max = a
        min = b
    else:
        max = b
        min = a
    div = GetGreatestCommonDivisor(min,max)
    return min * max / div

temp = 1
for i in range(1,21):
    temp = GetLeastCommonMultiple(i,temp)
print temp

本题旨在求最小公倍数。此算法有意思的是,它的精华在于如何求解两个正整数的最大公约数,有点围魏救赵的意思。

这里可以找到另外一些求解最小公倍数的方法。