[알고리즘] 유클리드 호제법(Uclidean algorithm) by javascript - 최대공약수 / 최소공배수 구하기 알고리즘

최대 공약수를 구하는 알고리즘인 유클리드 호제법에 대해 알아보자.

그리고 추가적으로 최소공배수까지 구하는 방법 역시 알아보자.

---

1. 최대공약수 구하기

우선 최대공약수란 두 수의 공통인 약수(공약수) 중에서 가장 큰 수를 최대공약수라고 부른다.

유클리드 호제법의 원리를 다음과 같이 설명한다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a> b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

무슨 소리인지 모르겠지만 일단 원리를 따라가보면 두 수(a, b)가 주어지고 이 둘을 나눈 나머지를 구하라는 의미 같다.

 

예를 들어 1071 과 1029 주어 졌다면 다음과 같은 원리를 따른다.

• (1071은 1029로 나누어 떨어지지 않기 때문에 둘을 나눈 나머지를 구한다.) 1071 % 1029 = 42
• (1029는 42로 나누어 떨어지지 않기 때문에 둘을 나눈 나머지를 구한다.) 1029 % 42 = 21
• (42는 21로 나누어 떨어지기 때문에) 결국 최대공약수는 21이다.

원리를 이제 이해했다면 이를 코드로 구현하기는 쉽다.

 

▷ 최대공약수 구하기 알고리즘 구현

// 1. 반복문으로 구현
function gcd(a, b) {
    while (b != 0) {
        let r = a % b;
        [a, b] = [b, r];
    }
    return a;
}

// 2. 재귀함수로 구현
function gcd(a, b) {
    return b ? gcd(b, a % b) : a;
}

---

2. 최소공배수 구하기

최소공배수란 두 수의 공통인 배수(공배수) 중에서 가장 작은 수를 최소공배수라고 부른다.

최소공배수의 성질 중에 "두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수로 나눈 것과 같다"라는 성질이 있는데 이는 위에서 최대공약수를 구한 알고리즘을 사용하면 손쉽게 구할 수 있다.

 

▷ 최소공배수 구하기 알고리즘 구현

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

function gcd(a, b) {
    return b ? gcd(b, a % b) : a;
}

 

---

참고 : 위키백과 - 유클리드_호제법

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