21

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 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

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?

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 :-)

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.

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.

4

14 に答える 14

20

答えは、因数分解や素数べき乗の点で派手なフットワークをまったく必要とせず、間違いなくエラトステネスのふるいも必要としません。

代わりに、ユークリッドのアルゴリズムを使用して 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))
于 2008-10-13T01:34:34.627 に答える
12

この問題は興味深いものです。任意の数値のセットのLCMを見つける必要がなく、連続した範囲が与えられるからです。エラトステネスのふるいのバリエーションを使用して、答えを見つけることができます。

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番目の観察結果は、このアルゴリズムは範囲の開始が2以下の場合にのみ機能することです。これは、範囲の開始より下の一般的な要因をふるいにかけようとしないためです。たとえば、RangeLCM（10、12）は、正しい660ではなく1320を返します。

3番目の観察結果は、他の回答に対してこの回答の時間を計ろうとした人は誰もいないということです。私の腸は、範囲が大きくなるにつれて、これはブルートフォースLCMソリューションよりも改善されると述べました。テストは私の腸が正しいことを証明しました、少なくともこれは一度。

アルゴリズムは任意の範囲では機能しないため、範囲が1から始まると想定して書き直しましたreduce。因子が生成されると結果を計算しやすくなるため、最後にtoの呼び出しを削除しました。新しいバージョンの関数は、より正確で理解しやすいと思います。

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の範囲で、ユークリッドのアルゴリズムは私の古い答えと新しい答えの両方を打ち負かします。1から100の範囲では、ふるいベースのアルゴリズム、特に最適化されたバージョンが先に進んでいることがわかります。

于 2008-10-09T04:14:07.313 に答える
10

範囲が1からNである限り、これに対する迅速な解決策があります。

重要な観察は、n（<N）が素因数分解 を持っている場合p_1^a_1 * p_2^a_2 * ... p_k * a_k、それはLCMにp_1^a_1and 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)関数を事前に計算することもできます。

編集：

最近の賛成票のため、他のリストされたアルゴリズムとの速度比較がどのように行われたかを確認するために、これを再検討することにしました。

JoeBeibersおよびMarkRansomsメソッドに対する、10k回の反復による範囲1-160のタイミングは次のとおりです。

ジョーズ：1.85秒マーク：3.26秒鉱山：0.33秒

これは、最大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)
于 2012-05-18T07:34:35.270 に答える
5

Haskell のワンライナー。

wideLCM = foldl lcm 1

これは、私自身の Project Euler Problem 5 で使用したものです。

于 2008-10-13T01:20:36.417 に答える
3

Haskellの場合：

listLCM xs =  foldr (lcm) 1 xs

あなたがリストを渡すことができるもの例：

*Main> listLCM [1..10]
2520
*Main> listLCM [1..2518]
266595767785593803705412270464676976610857635334657316692669925537787454299898002207461915073508683963382517039456477669596355816643394386272505301040799324518447104528530927421506143709593427822789725553843015805207718967822166927846212504932185912903133106741373264004097225277236671818323343067283663297403663465952182060840140577104161874701374415384744438137266768019899449317336711720217025025587401208623105738783129308128750455016347481252967252000274360749033444720740958140380022607152873903454009665680092965785710950056851148623283267844109400949097830399398928766093150813869944897207026562740359330773453263501671059198376156051049807365826551680239328345262351788257964260307551699951892369982392731547941790155541082267235224332660060039217194224518623199770191736740074323689475195782613618695976005218868557150389117325747888623795360149879033894667051583457539872594336939497053549704686823966843769912686273810907202177232140876251886218209049469761186661055766628477277347438364188994340512556761831159033404181677107900519850780882430019800537370374545134183233280000
于 2012-10-20T20:28:42.323 に答える
2

1 つまたは複数の数の最小公倍数は、すべての数の個別の素因数すべての積であり、各素数は、最小公倍数を取得する数に現れるすべての累乗の最大値の累乗になります。

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 です。 2^3 * 3^3 * 5^2 * 7^2。

于 2008-10-09T03:22:17.510 に答える
2 
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;
}
于 2011-04-08T20:20:03.717 に答える
1

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
于 2008-10-11T01:40:46.143 に答える
0

これが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]);
于 2015-04-21T21:44:23.740 に答える
0

これはおそらく、これまでに見た中で最もクリーンで最短の答えです (コード行の両方の観点から)。

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

于 2015-04-12T11:34:28.730 に答える
0

これが私の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)

ステップ 1 は、数値の素因数を取得します。ステップ 2 では、各要素が検出された最大回数のハッシュ テーブルを作成し、それらをすべて掛け合わせます。

于 2008-10-11T13:46:03.713 に答える
0

これが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;
}
于 2018-08-12T07:17:25.310 に答える
-1

@Alexanderのコメントを拡張する際に、数値を素数に因数分解し、重複を削除してから乗算すると、答えが得られることを指摘します。

たとえば、1 ～ 5 の素因数は 2、3、2、2、5 です。「4」の因子リストから重複した「2」を削除すると、2,2,3,5 になります。これらを掛け合わせると 60 が得られます。これがあなたの答えです。

前のコメントで提供された Wolfram リンクhttp://mathworld.wolfram.com/LeastCommonMultiple.htmlは、より正式なアプローチに入りますが、短いバージョンは上記のとおりです。

乾杯。

于 2008-10-09T03:19:16.580 に答える