找到一个数字范围的LCM [英] Finding the LCM of a range of numbers

问题描述

我的今天，读到一篇有趣的DailyWTF后所有的可能的答案......，它让我感兴趣的，足以挖掘出原来的论坛帖子它被提交。这让我想我会怎样解决这个有趣的问题 - 原来的问题是提出在项目欧拉的是：

I read an interesting DailyWTF post today, "Out of All The Possible Answers..." and it interested me enough to dig up the original forum post where it was submitted. This got me thinking how I would solve this interesting problem - the original question is posed on Project Euler as:

2520是最小的数目可以由每个被划分   从1到10的数字，没有任何剩余

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

什么是最小的数字，它是整除所有   从1到20的数字？

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

要改革这是一个程序问题，你将如何创建一个可以找到号码的任意列表的最小公倍数的函数？

To reform this as a programming question, how would you create a function that can find the Least Common Multiple for an arbitrary list of numbers?

我是非常糟糕的纯数学，尽管我对编程的兴趣，但我可以一点点谷歌搜索和一些试验后，解决这个问题。我很好奇什么其他的方法，因此用户可能需要。如果你愿意，张贴一些code以下，希望随着一个解释。请注意，虽然我敢肯定，库存在计算各种语言的GCD和LCM，我更感兴趣的是更多的东西比直接调用库函数:-)

I'm incredibly bad with pure math, despite my interest in programming, but I was able to solve this after a little Googling and some experimenting. I'm curious what other approaches SO users might take. If you're so inclined, post some code below, hopefully along with an explanation. Note that while I'm sure libraries exist to compute the GCD and LCM in various languages, I'm more interested in something that displays the logic more directly than calling a library function :-)

我最熟悉Python，C，C ++和Perl，但任何语言preFER是值得欢迎的。奖励积分用来说明其他数学挑战的人逻辑有像我自己。

I'm most familiar with Python, C, C++, and Perl, but any language you prefer is welcome. Bonus points for explaining the logic for other mathematically-challenged folks out there like myself.

修改：提交我发现这个类似的问题最小公倍数为3个或更多的数字后但得到的回答是基本相同的code，我已经想通了，有没有真正的解释，所以我觉得这是不够的不同平仓离场。

EDIT: After submitting I did find this similar question Least common multiple for 3 or more numbers but it was answered with the same basic code I already figured out and there's no real explanation, so I felt this was different enough to leave open.

推荐答案

这个问题很有趣，因为它不要求你找到任意一组数字的LCM，你给一个连续的范围内。您可以使用筛中找到了答案。

This problem is interesting because it doesn't require you to find the LCM of an arbitrary set of numbers, you're given a consecutive range. You can use a variation of the Sieve of Eratosthenes to find the answer.

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)

---

编辑：最近upvote让我重新审视这个答案是3岁以上。我的第一个看法是，我会写它今天有点不同，使用枚举例如。

---

A recent upvote made me re-examine this answer which is over 3 years old. My first observation is that I would have written it a little differently today, using enumerate for example.

第二观察是，这种算法只能如果该范围的起点是2或更小，因为它不试图筛出共同因素的范围的开始下面。例如，RangeLCM（10,12）返回1320而不是正确的660

The second observation is that this algorithm only works if the start of the range is 2 or less, because it doesn't try to sieve out the common factors below the start of the range. For example, RangeLCM(10, 12) returns 1320 instead of the correct 660.

第三个观察是，没有人试图时间向任何其他答案这个答案。我的直觉说，这将提高超过蛮力LCM解决方案的范围得到了较大。测试证明我的直觉正确的，至少这一次。

The third observation is that nobody attempted to time this answer against any other answers. My gut said that this would improve over a brute force LCM solution as the range got larger. Testing proved my gut correct, at least this once.

由于算法不任意范围内的工作，我重写了它的假设，范围从1开始我删除了在最后调用减少，作为这是比较容易计算结果作为生成的因素。我相信功能的新版本既更正确，更容易理解。

Since the algorithm doesn't work for arbitrary ranges, I rewrote it to assume that the range starts at 1. I removed the call to reduce at the end, as it was easier to compute the result as the factors were generated. I believe the new version of the function is both more correct and easier to understand.

def RangeLCM2(last):
    factors = 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

下面是对原来的解决方案，一些时间比较提出的乔·倍倍尔这就是所谓的 RangeEuclid 在我的测试。

Here are some timing comparisons against the original and the solution proposed by Joe Bebel which is called RangeEuclid in my tests.

>>> 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中的问题给出的范围，欧几里德的算法击败了我的两个旧的和新的答案。为1至100的范围内可以看到筛基于算法拉进取，特别是优化版本

For the range of 1 to 20 given in the question, Euclid's algorithm beats out both my old and new answers. For the range of 1 to 100 you can see the sieve-based algorithm pull ahead, especially the optimized version.

这篇关于找到一个数字范围的LCM的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！