Python练习题 033：Project Euler 005：最小公倍数

本题来自 Project Euler 第5题：https://projecteuler.net/problem=5

# Project Euler: 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?

# Answer: 232792560

# 求解2个数字的最大公约数 f(x,y)

def f(x,y):

    t = 1

    for i in range(1,min(x,y)+1):

        if x%i == 0 and y%i ==0:

            t = max(t, i)

    return t

m = 1

for i in range(1,21):

    #两个数字相乘，再除以其最大公约数，可得最小公倍数

    m = (m * i) // f(m, i)

print(m)

为了这题，我这数学渣真是想破了脑袋也没想出算法。后来只好借助网络手段，在 “Python实现Project Euler 5” 中了解到，原来求解 a,b 两个数字的最小公倍数，可以把 a,b 相乘，然后除以这两个数字的小大公约数。虽然算法有了，但作者写的代码俺实在看不懂（啥“辗转相除法”，唉……），只好照着描述的算法，写出了上面的代码（相比之下，我的代码繁复很多啊）：

先定义函数 f(x,y)，用来求解任意两个数字的最大公约数。思路是：先比校 x,y 得出更小的数字，然后从1到这个更小的数字，逐一拿来跟 x 和 y 除，如果都能整除，则表示是公约数，取最大的公约数即可。

之后就简单了，从 1 开始，两个两个地计算最小公倍数，结果再与下一个数字一起计算最小公倍数，算到 20 就能得出答案了。

---------------------

P.S.：最初的想法是，找到 1-20 之间的所有质数，相乘。后来发现乘完之后的数字根本无法被 20 整除。之后又试了好多办法，都不管用，我的数学真是没救了……

有谁能看懂 “Python实现Project Euler 5” 这篇文章里的代码的，求解释！