我今天读了一篇有趣的DailyWTF帖子"Out of All The Possible Answers..."，它对我很感兴趣，可以从中找到原始的forum post。这让我开始思考如何解决这个有趣的问题-原始问题在Project Euler上提出为:
要将其改写为编程问题，您将如何创建一个函数，该函数可以找到任意数字列表的最小公倍数？
尽管我对编程感兴趣，但我对纯数学却感到非常糟糕，但是经过一些谷歌搜索和一些实验之后，我就能解决这个问题。我很好奇用户可能会采用什么其他方法。如果您愿意，可以在下面发布一些代码，并附上解释。请注意，虽然我确定可以使用各种语言来计算GCD和LCM的库，但我对使显示逻辑比调用库函数更直接的事情更感兴趣:-)
我最熟悉Python，C，C++和Perl，但欢迎使用您喜欢的任何语言。奖励积分为其他像我一样受到数学挑战的人们解释逻辑。
编辑:提交后，我确实找到了类似的问题Least common multiple for 3 or more numbers，但是使用我已经弄清楚的相同基本代码进行了回答，并且没有真正的解释，因此我觉得这足够开放了。
最佳答案
这个问题很有趣，因为它不需要您查找任意数字集的LCM，您将获得一个连续的范围。您可以使用Sieve of Eratosthenes的变体来找到答案。
def RangeLCM(first, last):
factors = range(first, last+1)
for i in range(0, len(factors)):
if factors[i] != 1:
n = first + i
for j in range(2*n, last+1, n):
factors[j-first] = factors[j-first] / factors[i]
return reduce(lambda a,b: a*b, factors, 1)
编辑:最近的一次投票使我重新检查了这个已有3年历史的答案。我的第一个观察结果是，今天我使用
enumerate编写它时会有所不同。为了使其与Python 3兼容，需要进行一些小改动。第二个观察结果是，该算法仅在范围的起点等于或小于2时才起作用，因为它不会尝试筛选出范围起点以下的公因数。例如，RangeLCM(10，12)返回1320，而不是正确的660。
第三个观察结果是，没有人尝试将此答案与其他任何答案进行计时。我的直觉说，随着范围的扩大，这将比蛮力的LCM解决方案有所改善。测试证明我的直觉是正确的，至少这一次。
由于该算法不适用于任意范围，因此将其重写为假定范围从1开始。我删除了对
reduce的末尾调用，因为在生成因子时更容易计算结果。我相信该功能的新版本既更正确也更容易理解。def RangeLCM2(last):
factors = list(range(last+1))
result = 1
for n in range(last+1):
if factors[n] > 1:
result *= factors[n]
for j in range(2*n, last+1, n):
factors[j] //= factors[n]
return result
这是一些与Joe Bebel提出的解决方案和原始解决方案的时序比较，在我的测试中称为
RangeEuclid。>>> t=timeit.timeit
>>> t('RangeLCM.RangeLCM(1, 20)', 'import RangeLCM')
17.999292996735676
>>> t('RangeLCM.RangeEuclid(1, 20)', 'import RangeLCM')
11.199833288867922
>>> t('RangeLCM.RangeLCM2(20)', 'import RangeLCM')
14.256165588084514
>>> t('RangeLCM.RangeLCM(1, 100)', 'import RangeLCM')
93.34979585394194
>>> t('RangeLCM.RangeEuclid(1, 100)', 'import RangeLCM')
109.25695507389901
>>> t('RangeLCM.RangeLCM2(100)', 'import RangeLCM')
66.09684505991709
对于问题给出的1到20的范围，Euclid的算法胜过我的新老答案。对于1到100的范围，您可以看到基于筛子的算法，特别是优化版本。
关于algorithm - 查找一系列数字的LCM，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/185781/