代码之家 › 专栏 › 技术社区 › Jay

查找一系列数字的LCM

lcm math algorithm

Jay · 技术社区 · 16 年前

我今天读了一篇有趣的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 但它是用我已经想出的相同的基本代码来回答的,而且没有真正的解释,所以我觉得这已经足够不同了。

14 回复 | 直到 8 年前

Mark Ransom 6 年前

答案根本不需要在因式分解或素数方面有任何花哨的步法,当然也不需要埃拉托色尼的筛子。

相反,你应该通过使用欧几里德算法计算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))

Joe Bebel 16 年前

这个问题很有趣,因为它不需要你找到任意一组数字的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的范围,欧几里得的算法击败了我的新旧答案。对于1到100的范围,你可以看到基于筛选的算法领先,尤其是优化版本。

Michael Anderson 13 年前

只要范围在1到N之间,就有一个快速的解决方案。

关键的观察结果是,如果 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) 功能。

编辑:

由于最近的一次投票,我决定重新审视这个问题,看看与其他列出的算法的速度比较如何。

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

慢跑:1.85秒标记:3.26秒地雷:0.33秒

这是一个对数图,结果高达300。

A log-log graph with the results

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

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)

yfeldblum 16 年前

Haskell中的一行代码。

wideLCM = foldl lcm 1

这是我在Project Euler Problem 5中使用的。

Charlie 12 年前

在Haskell中:

listLCM xs =  foldr (lcm) 1 xs

你可以传递一个列表,例如:

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

yfeldblum 16 年前

一个或多个数的LCM是所有数中所有不同素数因子的乘积,每个素数都是该素数在其LCM中出现的所有幂的最大幂的幂。

比如说900=2^3*3^2*5^2,26460=2^2*3^3*5^1*7^2。 2的最大功率是3,3的最大功率为3,5的最大功率也是1,7的最大功率就是2,任何更高素数的最大功率都是0。因此,LCM为:264600=2^3*3^3*5^2*7^2。

sth 13 年前

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;
}

yfeldblum 16 年前

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

Kirk Strauser 16 年前

以下是我的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)

第一步得到一个数字的素数。第二步构建一个哈希表,记录每个因子被看到的最大次数,然后将它们相乘。

fixxxer 10 年前

这可能是我迄今为止看到的最干净、最短的答案(无论是从代码行数来看)。

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

Shazam 10 年前

这是我在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]);

Yup. 8 年前

这是我的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;
}

NEURON 7 年前

这是使用C Lang的解决方案

#include<stdio.h>
    int main(){
    int a,b,lcm=1,small,gcd=1,done=0,i,j,large=1,div=0;
    printf("Enter range\n");
    printf("From:");
    scanf("%d",&a);
    printf("To:");
    scanf("%d",&b);
    int n=b-a+1;
    int num[30];
    for(i=0;i<n;i++){
        num[i]=a+i;
    }
    //Finds LCM
    while(!done){
        for(i=0;i<n;i++){
            if(num[i]==1){
                done=1;continue;
            }
            done=0;
            break;
        }
        if(done){
            continue;
        }
        done=0;
        large=1;
        for(i=0;i<n;i++){
            if(num[i]>large){
                large=num[i];
            }
        }
        div=0;
        for(i=2;i<=large;i++){
            for(j=0;j<n;j++){
                if(num[j]%i==0){
                    num[j]/=i;div=1;
                }
                continue;
            }
            if(div){
                lcm*=i;div=0;break;
            }
        }
    }
    done=0;
    //Finds GCD
    while(!done){
        small=num[0];
        for(i=0;i<n;i++){
            if(num[i]<small){
                small=num[i];
            }
        }
        div=0;
        for(i=2;i<=small;i++){
            for(j=0;j<n;j++){
                if(num[j]%i==0){
                    div=1;continue;
                }
                div=0;break;
            }
            if(div){
                for(j=0;j<n;j++){
                    num[j]/=i;
                }
                gcd*=i;div=0;break;
            }
        }
        if(i==small+1){
            done=1;
        }
    }
    printf("LCM = %d\n",lcm);
    printf("GCD = %d\n",gcd);
    return 0;
}

-1

warren 16 年前

在扩展@Alexander的评论时,我想指出,如果你能将数字分解为素数,删除重复项,然后相乘,你就会得到答案。

例如,1-5的素数为2,3,2,2,5。从“4”的因子列表中删除重复的“2”,得到2,2,3,5。将它们相乘得到60,这就是你的答案。

在前面的评论中提供的Wolfram链接, http://mathworld.wolfram.com/LeastCommonMultiple.html 采用了一种更正式的方法,但简短的版本在上面。

干杯。