[알고리즘] 최대공약수, 최소공배수 구하기

요즘 프로그래머스 코테를 풀어보고있는데 최소공배수, 최대공약수를 활용하면 쉽게 풀릴 문제들이 많이 보여서 한번 제대로 정리하고 넘어가려한다.
분명 초등학교에서 배웠던 것 같은데 이상하게 새롭다. 최대공약수, 최소공배수가 도대체 뭘까?

약수와 공약수

1. 약수(Divisor) : 주어진 수를 나누어 떨어지게 하는 수
2. 공약수(CD, Common Divisor) : 두 수 이상의 여러 수 중 공통된 약수

최대공약수 (GCD, Greatest Common Divisor)

: 두 자연수의 공통된 약수 중 가장 큰 수

ex. 15와 18의 최대공약수 구하기

• 15의 약수 : 1, 3, 5, 15
• 18의 약수 : 1, 2, 3, 6, 9, 18
  ↪ 공약수: 1, 3
  ↪ 최대공약수 : 3

※ 최대공약수 구하기 코드

: 2부터 두 수(a, b)의 최소값 사이의 모든 숫자로 나눠보면서 최대값 구하기

const getGcd = (a, b) => {
	let gcd = 1; // 최대공약수
    
    for (let i = 2; i <= Math.min(a, b); i++) {
    	if (a % i === 0 && b % i === 0) {
        	gcd = i;
        }
    }
    return gcd;
}

---

최소공배수 (LCM, Lowest Common Multiple)

두 자연수의 공통된 배수 중 가장 작은 수

ex. 12와 18의 최소공배수 구하기

• 12의 배수 : 12, 24, 36, 48, 60 • • •
• 18의 배수 : 18, 36, 54, 72, 90 • • •
  ↪ 공배수: 36 • • •
  ↪ 최소공배수 : 36

※ 최소공배수 구하기 코드

: 두 수의 곱을 두 수의 최대공약수로 나누기
↪ 최소공배수 최대공약수 = a b
↪ 최소공배수 = a * b / 최대공약수

const getLcm = (a, b) => {
	let gcd = 1; // 최대공약수
    let lcm = 1; // 최소공배수
    
    for (let i = 2; i <= Math.min(a, b); i++) {
    	if (a % i === 0 && b % i === 0) {
        	gcd = i;
        }
    }
    
    lcm = (a * b) / gcd;
    
    return lcm;
}

---

하지만 기원전 3세기경에 고대 그리스 수학자인 유클리드(Euclid)에 의해 발견된 굉장한 알고리즘을 사용하면 누구보다 빠르게 최대공약수를 구해볼 수 있다. 고로 "유클리드 호제법"이라는 알고리즘에 대해 알아보자.

유클리드 호재법

두 수의 최대공약수를 구하는 알고리즘

※ 호재법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

원리

두 수를 나눈 나머지를 r이라고 할 때, 두 수 중 작은 수와 r의 최대공약수가 두 수의 최대공약수와 같다는 것을 이용하여, 과정을 반복하다가 나머지가 0이 될 때 나누는 수가 두 수의 최대공약수가 된다.

1. 큰 수(a)를 작은 수(b)로 나누기 (a > b면, a / b)
2. 나머지가 0이 아니면, 나누는 수(b)를 나머지(r)로 나눈다. (b / r)
3. 계속 반복해서 나머지가 0이면, 나누는 수가 최대공약수

자바스크립트 코드로 구현해보면 이렇다.

최대공약수(GCD) 구하기

1) while문으로 구현

//
const gcd = (a, b) => {
	while (b > 0) {
    	let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
};

2) 재귀함수로 구현

const gcd = (a, b) => a % b ? gcd(b, a % b) : b;

최소공배수(LCM) 구하기

• 최소공배수 = a * b / 최대공약수

const lcm = (a, b) => a * b / gcd(a, b);