[백준 2609] 최대공약수와 최소공배수 [C]

백준 - 2609

---

풀이

유클리드 호제법은 최대공약수를 구하는 알고리즘이다.

1. 두 수 N, M (N > M)을 입력받는다.
2. N을 M으로 나누었을 때의 몫과 나머지가 N, M이 되며 이 과정을 나머지가 0이 될 때 까지 반복한다.\
3. 나머지가 0이 될때의 N(몫)이 최대공약수이다.
4. 두 수 N, M의 곱은 최대공약수(GCD)와 최소공배수(LCM)의 곱과 같다.

---

소스코드

#include <stdio.h>
int euclidean_gcd(int n, int m){
    return m ? euclidean_gcd(m, n%m) : n;
}
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    int gcd = euclidean_gcd(n, m);
    printf("%d\n%d", gcd, n*m / gcd);
}

---

출처 및 참고자료

2609번: 최대공약수와 최소공배수

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