查找一系列数字的最小公倍数

今天我读了一篇有趣的DailyWTF帖子,"Out of All the Possible Answers ...",我对它感兴趣,足以挖掘提交它的原始论坛帖子.这让我想到如何解决这个有趣的问题 - 最初的问题是在Project Euler上提出的:

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

可以被1到20的所有数字整除的最小数字是多少？

要将此作为一个编程问题进行改革,您将如何创建一个能够为任意数字列表找到最小公倍数的函数？

尽管我对编程很感兴趣,但我对纯数学的表现非常糟糕,但是我可以通过一些谷歌搜索和一些实验来解决这个问题.我很好奇SO用户可能采取的其他方法.如果你这么倾向,请在下面发布一些代码,希望还有一个解释.请注意,虽然我确定存在用于以各种语言计算GCD和LCM的库,但我更感兴趣的是比调用库函数更直接地显示逻辑的东西:-)

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

编辑:提交后我确实发现这个类似的问题3个或更多数字的最小公倍数,但它回答了我已经想出的相同的基本代码,并没有真正的解释,所以我觉得这是不同的,足以让我们开放.

1> 小智..：

---

答案在保理或主要权力方面根本不需要任何花哨的步法,而且大多数情况下都不需要Eratosthenes筛选.

相反,您应该通过使用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))

---

使用return a*(b/gcd)或return(a/gcd)*b.因为a*b可以是一个很大的数字.

2> Mark Ransom..：

---

这个问题很有意思,因为它不需要你找到一组任意数字的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)

---

编辑:最近的一个upvote让我重新审视这个超过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的范围,您可以看到基于筛选的算法,尤其是优化版本.

3> Michael Ande..：

---

只要范围是1到N,就可以快速解决这个问题.

关键的观察是,如果n(p_1^a_1 * p_2^a_2 * ... p_k * a_k,那么这将有助于一模一样的因素对LCM为p_1^a_1和p_2^a_2,... p_k^a_k.并且这些功率中的每一个也在1到N范围内.因此,我们只需要考虑小于N的最高纯素数.

例如20我们有

2^4 = 16 < 20
3^2 = 9  < 20
5^1 = 5  < 20
7
11
13
17
19

将所有这些主要权力相乘,我们得到了所需的结果

2*2*2*2*3*3*5*7*11*13*17*19 = 232792560

所以在伪代码中:

def lcm_upto(N):
  total = 1;
  foreach p in primes_less_than(N):
    x=1;
    while x*p <= N:
      x=x*p;
    total = total * x
  return total

现在,您可以调整内部循环以稍微不同地工作以获得更高的速度,并且您可以预先计算primes_less_than(N)函数.

编辑:

由于最近的一个upvote我决定重新审视这个,看看与其他列出的算法的速度比较如何.

对于Joe Beibers和Mark Ransoms方法,针对范围1-160和10k迭代的时序如下:

Joes:1.85s Marks:3.26s Mine:0.33s

这是一个日志日志图,结果最多为300.

我的测试代码可以在这里找到:

import timeit


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


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

def EuclidLCM(last):
    return reduce(lcm,range(1,last+1))

primes = [
 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 
 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 
 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 
 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 
 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 
 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 
 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 
 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 
 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 
 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 
 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 
 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 
 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 
 947, 953, 967, 971, 977, 983, 991, 997 ]

def FastRangeLCM(last):
    total = 1
    for p in primes:
        if p>last:
            break
        x = 1
        while x*p <= last:
            x = x * p
        total = total * x
    return total


print RangeLCM2(20)
print EculidLCM(20)
print FastRangeLCM(20)

print timeit.Timer( 'RangeLCM2(20)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(20)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(20)', "from __main__ import FastRangeLCM" ).timeit(number=10000)

print timeit.Timer( 'RangeLCM2(40)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(40)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(40)', "from __main__ import FastRangeLCM" ).timeit(number=10000)

print timeit.Timer( 'RangeLCM2(60)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(60)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(60)', "from __main__ import FastRangeLCM" ).timeit(number=10000)

print timeit.Timer( 'RangeLCM2(80)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(80)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(80)', "from __main__ import FastRangeLCM" ).timeit(number=10000)

print timeit.Timer( 'RangeLCM2(100)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(100)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(100)', "from __main__ import FastRangeLCM" ).timeit(number=10000)

print timeit.Timer( 'RangeLCM2(120)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(120)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(120)', "from __main__ import FastRangeLCM" ).timeit(number=10000)

print timeit.Timer( 'RangeLCM2(140)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(140)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(140)', "from __main__ import FastRangeLCM" ).timeit(number=10000)

print timeit.Timer( 'RangeLCM2(160)', "from __main__ import RangeLCM2").timeit(number=10000)
print timeit.Timer( 'EuclidLCM(160)', "from __main__ import EuclidLCM" ).timeit(number=10000)
print timeit.Timer( 'FastRangeLCM(160)', "from __main__ import FastRangeLCM" ).timeit(number=10000)

---

如果pow(3,x-1,x)== 1 =,你可以说`primes = [2,3] + [x代表范围内的x(5,1000,2),而不是那个冗长的素数列表<1000 = pow(2,x-1,x)]`,在不到一毫秒的时间内执行.

4> yfeldblum..：

---

Haskell中的单线程.

wideLCM = foldl lcm 1

这就是我用于自己的Project Euler Problem 5的原因.