寻找一系列数字的LCM

Question

我今天看了一篇有趣的DailyWTF帖子，"Out of All The Possible Answers..."，它对我感兴趣，足以挖掘提交它的原始forum post。这让我想我会怎么解决这个有趣的问题 - 原来的问题被提出在Project Euler为：

2520是可以由每个 数字没有任何除尽从1到10的最小数目。

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

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

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

我最熟悉Python，C，C++和Perl，但欢迎您选择任何您喜欢的语言。附加点来解释像我这样的其他数学挑战的人的逻辑。

编辑：提交我发现这个类似的问题Least common multiple for 3 or more numbers但它与我已经想通了，有没有真正的解释相同的基本代码回答后，所以我觉得这是不够的不同平仓离场。

Answer 1

这个问题很有趣，因为它不要求你找到任意一组数字的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。

第二个观察结果是，如果范围的起始点为2或更小，此算法才起作用，因为它不会尝试筛选范围起点以下的公因子。例如，RangeLCM（10,12）返回1320而不是正确的660.

第三个观察结果是，没有人试图对任何其他答案计时。我的直觉说，随着射程越来越大，这可能会超越强力LCM解决方案。测试证明我的直觉是正确的，至少这是一次。

由于该算法不适用于任意范围，因此我将其重写为假定范围从1开始。我在最后删除了对reduce的调用，因为在生成因子时更容易计算结果。我相信新版本的功能更加正确，更易于理解。

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 

下面是对原有和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的范围内，欧几里德的算法击败了我的两个新老答案。对于1到100的范围，您可以看到基于筛选的算法拉开，尤其是优化版本。

Answer 2

在@亚历山大的评论中，我指出如果你可以将数字归因于他们的素数，删除重复，然后乘以，你会得到你的答案。

例如，1-5的主因子为2,3,2,2,5。从'4'的因子列表中删除重复的'2'，并且您有2,2,3,5。将它们相乘得出60，这是你的答案。

先前评论http://mathworld.wolfram.com/LeastCommonMultiple.html中提供的Wolfram链接采用更正式的方法，但简短版本位于上方。

干杯。

Answer 3

一个或多个数字的LCM是所有数字中所有不同素数因子的乘积，每个素数都是该素数出现在数字中的所有幂的最大值的乘方LCM的。表示900 = 2^3 * 3^2 * 5^2,26460 = 2^2 * 3^3 * 5^1 * 7^2。 2的最大功率为3，最大功率为3，最大功率为5，最大功率为7，最大功率为0. 因此，LCM为： 264600 = 2^3 * 3^3 * 5^2 * 7^2。

Answer 4

Haskell中的算法。这是我现在思考算法思维的语言。这看起来可能很奇怪，复杂，并且是不合理的 - 欢迎来到Haskell！

primes :: (Integral a) => [a] 
--implementation of primes is to be left for another day. 

primeFactors :: (Integral a) => a -> [a] 
primeFactors n = go n primes where 
    go n ps@(p : pt) = 
     if q < 1 then [] else 
     if r == 0 then p : go q ps else 
     go n pt 
     where (q, r) = quotRem n p 

multiFactors :: (Integral a) => a -> [(a, Int)] 
multiFactors n = [ (head xs, length xs) | xs <- group $ primeFactors $ n ] 

multiProduct :: (Integral a) => [(a, Int)] -> a 
multiProduct xs = product $ map (uncurry (^)) $ xs 

mergeFactorsPairwise [] bs = bs 
mergeFactorsPairwise as [] = as 
mergeFactorsPairwise a@((an, am) : _) b@((bn, bm) : _) = 
    case compare an bn of 
     LT -> (head a) : mergeFactorsPairwise (tail a) b 
     GT -> (head b) : mergeFactorsPairwise a (tail b) 
     EQ -> (an, max am bm) : mergeFactorsPairwise (tail a) (tail b) 

wideLCM :: (Integral a) => [a] -> a 
wideLCM nums = multiProduct $ foldl mergeFactorsPairwise [] $ map multiFactors $ nums 

Answer 5

这里是我的Python刺吧：

#!/usr/bin/env python 

from operator import mul 

def factor(n): 
    factors = {} 
    i = 2 
    while i <= n and n != 1: 
     while n % i == 0: 
      try: 
       factors[i] += 1 
      except KeyError: 
       factors[i] = 1 
      n = n/i 
     i += 1 
    return factors 

base = {} 
for i in range(2, 2000): 
    for f, n in factor(i).items(): 
     try: 
      base[f] = max(base[f], n) 
     except KeyError: 
      base[f] = n 

print reduce(mul, [f**n for f, n in base.items()], 1) 

第一步得到了许多的首要因素。第二步建立每个因子被看到的最大次数的哈希表，然后将它们全部相乘。

Answer 6

Haskell中的单线程。

wideLCM = foldl lcm 1 

这是我用我自己的项目欧拉问题5.

Answer 7

答案不需要任何花哨的脚法在保理或总理权力方面可言，当然也最不需要筛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)) 

Answer 8

print "LCM of 4 and 5 = ".LCM(4,5)."\n"; 

sub LCM { 
    my ($a,$b) = @_;  
    my ($af,$bf) = (1,1); # The factors to apply to a & b 

    # Loop and increase until A times its factor equals B times its factor 
    while ($a*$af != $b*$bf) { 
     if ($a*$af>$b*$bf) {$bf++} else {$af++}; 
    } 
    return $a*$af; 
} 

Answer 9

有一个快速的解决方案于此，只要该范围是1到N.

关键的观察是，如果n（< N）有因式分解p_1^a_1 * p_2^a_2 * ... p_k * a_k， 那么它将作为p_1^a_1和p_2^a_2，... p_k^a_k贡献一模一样的因素对LCM。而且这些权力中的每一个也都在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 

现在你可以调整内部环路窝rk略有不同，以获得更多速度，并且您可以预先计算primes_less_than(N)函数。

编辑：

由于最近给予好评我decideded重温这一点，看到与其他上市算法的速度对比如何。是

时序范围1-160用10k迭代，对乔Beibers和马克赎金方法如下：

乔斯：1.85s 商标：3.26s 矿：0.33s

这里有一个日志-log图的结果达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) 

Answer 10

在Haskell：

listLCM xs = foldr (lcm) 1 xs 

，您可以通过列表例如：

*Main> listLCM [1..10] 
2520 
*Main> listLCM [1..2518] 
266595767785593803705412270464676976610857635334657316692669925537787454299898002207461915073508683963382517039456477669596355816643394386272505301040799324518447104528530927421506143709593427822789725553843015805207718967822166927846212504932185912903133106741373264004097225277236671818323343067283663297403663465952182060840140577104161874701374415384744438137266768019899449317336711720217025025587401208623105738783129308128750455016347481252967252000274360749033444720740958140380022607152873903454009665680092965785710950056851148623283267844109400949097830399398928766093150813869944897207026562740359330773453263501671059198376156051049807365826551680239328345262351788257964260307551699951892369982392731547941790155541082267235224332660060039217194224518623199770191736740074323689475195782613618695976005218868557150389117325747888623795360149879033894667051583457539872594336939497053549704686823966843769912686273810907202177232140876251886218209049469761186661055766628477277347438364188994340512556761831159033404181677107900519850780882430019800537370374545134183233280000 

Answer 11

这可能是最清洁，最简单的回答（无论是在代码行方面），我”到目前为止已经看到。

def gcd(a,b): return b and gcd(b, a % b) or a 
def lcm(a,b): return a * b/gcd(a,b) 

n = 1 
for i in xrange(1, 21): 
    n = lcm(n, i) 

来源：http://www.s-anand.net/euler.html

Answer 12

这是我在JavaScript的答案。我首先从素数中找到了这个问题，并开发了一个可重用代码的好函数来寻找素数，并找出主要因素，但最终决定这种方法更简单。

没有什么独特之处我的回答是不是上面贴的，它只是在Javascript中，我没有具体看。

//least common multipe of a range of numbers 
function smallestCommons(arr) { 
    arr = arr.sort(); 
    var scm = 1; 
    for (var i = arr[0]; i<=arr[1]; i+=1) { 
     scm = scd(scm, i); 
    } 
    return scm; 
} 


//smallest common denominator of two numbers (scd) 
function scd (a,b) { 
    return a*b/gcd(a,b); 
} 


//greatest common denominator of two numbers (gcd) 
function gcd(a, b) { 
    if (b === 0) { 
     return a; 
    } else { 
     return gcd(b, a%b); 
    } 
}  

smallestCommons([1,20]); 

Answer 13

这里是我的JavaScript的解决方案，我希望你觉得它易于遵循：

function smallestCommons(arr) { 
    var min = Math.min(arr[0], arr[1]); 
    var max = Math.max(arr[0], arr[1]); 

    var smallestCommon = min * max; 

    var doneCalc = 0; 

    while (doneCalc === 0) { 
    for (var i = min; i <= max; i++) { 
     if (smallestCommon % i !== 0) { 
     smallestCommon += max; 
     doneCalc = 0; 
     break; 
     } 
     else { 
     doneCalc = 1; 
     } 
    } 
    } 

    return smallestCommon; 
}