目录

欧拉工程第五解

目录

第五解:

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?

解:

```python #为简洁明了,此处不作校验 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 ```

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

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