algorithm - 查找一系列数字的 LCM

Question

我今天读了一篇有趣的 DailyWTF 帖子，"Out of All The Possible Answers..."这让我很感兴趣，可以挖掘出原来的 forum post提交的地方。这让我开始思考如何解决这个有趣的问题——最初的问题是在 Project Euler 上提出的。如:

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?

要将其改造成一个编程问题，您将如何创建一个可以找到任意数字列表的最小公倍数的函数？

尽管我对编程很感兴趣，但我的纯数学非常糟糕，但经过一些谷歌搜索和一些实验后，我能够解决这个问题。我很好奇 SO 用户可能会采取哪些其他方法。如果您愿意，请在下面发布一些代码，并附上解释。请注意，虽然我确定存在以各种语言计算 GCD 和 LCM 的库，但我更感兴趣的是比调用库函数更直接地显示逻辑的东西:-)

我最熟悉 Python、C、C++ 和 Perl，但欢迎使用您喜欢的任何语言。为像我这样的其他数学挑战者解释逻辑的奖励积分。

编辑:提交后我确实发现了这个类似的问题Least common multiple for 3 or more numbers但它是用我已经想出的相同基本代码回答的，没有真正的解释，所以我觉得这有足够的不同，可以保持开放。

Answer 1

在因式分解或素数幂方面，答案根本不需要任何花哨的步法，而且最肯定不需要埃拉托色尼筛法。

相反，您应该使用 Euclid 算法(不需要因式分解，实际上速度要快得多)来计算 GCD 来计算单个对的 LCM:

def lcm(a,b):
    gcd, tmp = a,b
    while tmp != 0:
        gcd,tmp = tmp, gcd % tmp
    return a*b/gcd

然后你可以使用上面的 lcm() 函数找到总的 LCM 我减少数组:

reduce(lcm, range(1,21))