查找一系列数字的LCM

小编典典

查找一系列数字的LCM

algorithm

我今天读了一篇有趣的DailyWTF帖子，“从所有可能的答案中……”，它引起了我足够的兴趣，以找出最初提交该帖子的论坛帖子。这让我开始思考如何解决这个有趣的问题-
最初的问题在欧拉计划中提出：

2520是可以除以1到10的每个数字而没有任何余数的最小数字。

能被1到20的所有数字平均整除的最小数字是多少？

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

尽管我对编程感兴趣，但我对纯数学却感到非常糟糕，但是经过一些谷歌搜索和一些实验之后，我就能解决这个问题。我很好奇用户可能会采用什么其他方法。如果您愿意，可以在下面发布一些代码，并希望附上说明。请注意，尽管我确定可以使用各种语言来计算GCD和LCM的库，但我对使显示逻辑比调用库函数更直接的事情更感兴趣：-)

我最熟悉Python，C，C ++和Perl，但欢迎使用您喜欢的任何语言。奖励积分用于解释其他像我一样受到数学挑战的人们的逻辑。

编辑
：提交后，我确实找到了类似的问题3个或更多数字的最小公倍数，但是使用我已经弄清楚的相同基本代码进行了回答，并且没有真正的解释，所以我觉得这足够不同了，可以打开。

阅读 279

2020-07-28

共1个答案

小编典典

这个问题很有趣，因为它不需要您查找任意数字集的LCM，您将获得一个连续的范围。您可以使用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

这是一些与JoeBebel提出的原始解决方案和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的范围，您可以看到基于筛子的算法，特别是优化版本。

2020-07-28