[algorithm] 3 개 이상의 숫자에 대한 최소 공배수

여러 숫자의 최소 공배수를 어떻게 계산합니까?

지금까지 나는 두 숫자 사이에서만 계산할 수있었습니다. 그러나 3 개 이상의 숫자를 계산하기 위해 확장하는 방법을 모릅니다.

지금까지 이것은 내가 한 방법입니다

LCM = num1 * num2 /  gcd ( num1 , num2 )

gcd는 숫자의 최대 공약수를 계산하는 함수입니다. 유클리드 알고리즘 사용

그러나 3 개 이상의 숫자에 대해 계산하는 방법을 알 수 없습니다.



답변

두 숫자의 LCM을 반복적으로 계산하여 두 숫자 이상의 LCM을 계산할 수 있습니다.

lcm(a,b,c) = lcm(a,lcm(b,c))


답변

파이썬 (modified primes.py )에서 :

def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)

def lcmm(*args):
    """Return lcm of args."""
    return reduce(lcm, args)

용법:

>>> lcmm(100, 23, 98)
112700
>>> lcmm(*range(1, 20))
232792560

reduce()그런 식으로 작동 합니다 :

>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)


답변

ECMA 스타일 구현은 다음과 같습니다.

function gcd(a, b){
    // Euclidean algorithm
    var t;
    while (b != 0){
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

function lcm(a, b){
    return (a * b / gcd(a, b));
}

function lcmm(args){
    // Recursively iterate through pairs of arguments
    // i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))

    if(args.length == 2){
        return lcm(args[0], args[1]);
    } else {
        var arg0 = args[0];
        args.shift();
        return lcm(arg0, lcmm(args));
    }
}


답변

나는 이것 (C #)과 함께 갈 것이다.

static long LCM(long[] numbers)
{
    return numbers.Aggregate(lcm);
}
static long lcm(long a, long b)
{
    return Math.Abs(a * b) / GCD(a, b);
}
static long GCD(long a, long b)
{
    return b == 0 ? a : GCD(b, a % b);
}

언뜻보기 에이 코드가 수행하는 작업이 너무 명확하지 않기 때문에 몇 가지 설명이 필요합니다.

집계는 Linq 확장 방법이므로 System.Linq를 사용하여 참조에 추가하는 것을 잊을 수 없습니다.

집계는 누적 함수를 얻으므로 IEnumerable에서 lcm (a, b, c) = lcm (a, lcm (b, c)) 속성을 사용할 수 있습니다. 집계에 대한 추가 정보

GCD 계산은 유클리드 알고리즘을 사용 합니다 .

lcm 계산은 Abs (a * b) / gcd (a, b)를 사용합니다 . 최대 공약수의 감소를 참조하십시오 .

도움이 되었기를 바랍니다,


답변

방금 Haskell에서 이것을 알아 냈습니다.

lcm' :: Integral a => a -> a -> a
lcm' a b = a`div`(gcd a b) * b
lcm :: Integral a => [a] -> a
lcm (n:ns) = foldr lcm' n ns

나는 심지어 gcdPrelude에서만 찾기 위해 내 자신의 함수 를 작성하는 데 시간이 걸렸다 ! 오늘 나를 위해 많은 학습 : D


답변

gcd에 대한 함수가 필요하지 않은 일부 Python 코드 :

from sys import argv

def lcm(x,y):
    tmp=x
    while (tmp%y)!=0:
        tmp+=x
    return tmp

def lcmm(*args):
    return reduce(lcm,args)

args=map(int,argv[1:])
print lcmm(*args)

터미널에서 보이는 모습은 다음과 같습니다.

$ python lcm.py 10 15 17
510


답변

다음은 1에서 20까지의 정수의 LCM을 반환하는 Python one-liner (임포트 계산 제외)입니다.

Python 3.5 이상 가져 오기 :

from functools import reduce
from math import gcd

파이썬 2.7 수입품 :

from fractions import gcd

일반적인 논리 :

lcm = reduce(lambda x,y: x*y // gcd(x, y), range(1, 21))

모두 있습니다 파이썬 2파이썬 3 , 연산자 우선 순위 규칙이 있음을 지시 *하고 //연산자가 동일한 우선 순위를 가질, 그들은에서 적용 할 수 있도록 왼쪽에서 오른쪽으로. 따라서 x*y // z의미는 (x*y) // z아닙니다 x * (y//z). 이 둘은 일반적으로 다른 결과를 생성합니다. 이것은 플로트 분할에 대해서는 중요하지 않지만 바닥 분할에 대해서는 중요 합니다.