[Javascript ] 최대공약수와 최소공배수

[Javascript ] 최대공약수와 최소공배수

 

최대공약수 (GCD : the Greatest Common Denominator)

간단히 말해 최대공약수란  두 수의 공통된 약수 (공약수) 중 가장 큰 값  을 말한다.

 

만약 최대공약수를 직접 구현하고자 한다면 두 수를 나눴을 때 나머지가 0 이 되는 수들을 찾고 그 중 가장 큰 값을 구하면 된다.

const GCD = (num1, num2) => {
    let gcd = 1;

    for(let i=2; i<=Math.min(num1, num2); i++){
        if(num1 % i === 0 && num2 % i === 0){
            gcd = i;
        }
    }

    return gcd;
}

 

for 문으로 2부터 두 수 중 작은 숫자까지 두 숫자 모두 나머지가 0 인 것을 최대공약수로 한다. 

 

유클리드 호제법을 이용한 최대공약수 구하기 ⭐⭐⭐

이 방법을 간단하게 구현한 것이 유클리드 호제법을 이용하는 것이다. 유클리드 호제법을 간단하게 기본 원리를 설명하자면  num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것이다.

 

이를 이용해 구현하면 다음과 같다.

const GCD = (num1, num2) => (num2 > 0 ? GCD(num2, num1 % num2) : num1);

 

최대공약수 (LCM : the Least Common Multiple)

간단히 말해 최소공배수는 두 수의 양의 공배수 중 가장 작은 값을 말한다.

 

최소공배수를 구현하는 방식은 두 수를 곱하고 이를 최대공약수로 나눠주면 된다. 구현하면 다음과 같다.

const GCD = (num1, num2) => (num2 > 0 ? GCD(num2, num1 % num2) : num1);
const LCM = (num1, num2) => (num1 * num2) / GCD(num1, num2);

 

이렇게 간단하게 최대공약수와 최소공배수 구하는 방식에 대해 알아보았습니다.

 

---

<참고> 최대공약수, 최소공배수 : https://pabeba.tistory.com/76