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

时间:2023-02-23 07:31:30

本题来自 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” 这篇文章里的代码的,求解释!