[알고리즘] 유클리드 알고리즘(최대공약수, 최소공배수 구하기)

 일반적으로 최대공약수(Greatest Common Factor)와 최소공배수(Lowest Common Multiple)를 구할 때 소인수분해를 해서 구한다. 하지만 프로그래밍을 통해서 구할 때는 특정한 알고리즘 없이 직접적으로 구하기 까다롭다.

여기서 유클리드 알고리즘은 최대공약수를 구하는 특별한 알고리즘이다!

※ 유클리드 알고리즘이란?
주어진 두 수 사이에 최대공약수(GCD)를 구하는 알고리즘

---

유클리드 알고리즘은 "두 수 A, B가 주어졌을 때(단 A > B) A를 B로 나눈 나머지 r에 대해서 GCD(A, B) = GCD(B, r)이고, 여기서 나머지 r이 0이면 B가 두 수의 최대공약수이다!"라는 원리를 이용한 알고리즘이다.

 

알고리즘을 구현하는 방법은 재귀를 이용하는 방법과 반복문을 이용하는 방법 두 가지가 있다!

 반복문

int GCD(int a, int b){
    int r = a % b;
    while(True) {
        if (r == 0) return b;
        a = b;
        b = r;
    }
}

int GCD(int a, int b){
    if (b == 0) return a;
    else return GCD(b, a%b);
}

유클리드 알고리즘은 최대공약수만 구할 수 있다. 그렇다면 어떻게 최소공배수를 구할 수 있을까?

특별한 알고리즘 없이 GCD와 LCM 사이의 관계를 이해하면 된다!

 

두 수의 최대공약수를 G라고 했을 때,

A = G × a

B = G × b

최대공약수 = G

최소공배수 = G × a × b이다.

따라서 두 수의 곱은 최대공약수와 최소공배수의 곱과 같다!

 

이를 통해서, 최소 공배수를 구할 때는 두 수를 곱한 값에서 최대공약수를 나눠주면 된다!