최대공약수와 최소공배수 알고리즘 - 유클리드 호제법 (자바스크립트)

| 최대공약수와 최소공배수

60과 48의 최대공약수는 좌측의 값들을 곱한 2 * 2 * 3 = 12 이고, 최소공배수는 12 * 5 * 4 = 240이다.

따라서, 최대공약수(Greatest Common Divisor, GCD)와 최소공배수(Lowest Common Multiple, LCM)를 곱한 값은

주어진 두 수의 곱과 같다는 식이 성립된다.

 

| 최대공약수 구하기, 유클리드 호제법

유클리드 호제법이란 자연수의 최대공약수를 구하는 알고리즘의 하나이다.

호제법이란 두 수가 서로(互) 상대방 수를 나누어(除)서 원하는 수를 얻는 알고리즘을 나타낸다.

 

2개의 자연수 a, b에 대해서 a가 b보다 클 때 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는

b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수라는 것을 이용해 유클리드 호제법이 성립된다.

 

예시

위 그림과 같이 60과 48의 최대공약수를 유클리드 호제법으로 구해보자.

60과 48중 60이 더 크기 때문에 a = 60, b = 48로 하고 계산한다.
60 % 48 = 12 이므로 r = 12라 하고, 60과 48의 최대공약수는 48과 12의 최대공약수와 같게 된다.

다시 48과 12를 나누면 나머지가 0이 되기 때문에 나누는 수인 12가 최대공약수가 된다.

60 % 48 = 12    // a = 60, b = 48
48 % 12 = 0     // a = 48, b = 12

// 12는 60과 48의 최대공약수

 

구현

이를 코드로 구현하게 되면 재귀함수나 반복문으로 작성할 수 있다.

// 재귀함수
function gcd(a, b) {
	 return b == 0 ? a : gcd(b, a % b);
}

// 반복문
function gcd(a, b) {
    while( b !== 0 ){
        let temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}

 

위의 예시와 같이 b는 a로, a와 b를 나눈 나머지는 b로 들어가며 계산이 반복되고, 이는 a와 b를 나눈 나머지 즉, b 값이 0이 될 때까지 진행된다.

 

| 최소공배수

최소공배수는 최대공약수를 구했다면, 주어진 두 수의 곱 = 최대공약수 * 최소공배수 라는 식으로 쉽게 구할 수 있다.

최소공배수 = 두 수의 곱 / 최대공약수

 

구현

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

 

LINK

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전