[BaekJoon/백준] 2609번

최소공배수 , 최대공약수를 찾으라는 문제.

 

최소공배수를 위한 방법으로는 '유클리드 호제법'을 이용하면 된다.

 

유클리드 호제법

(A, B)의 최대공약수는 (B, A % B)의 최대공약수와 같다. 이 과정의 반복 속에 나머지가 0이 되었을 때, 나누는 수가 두 수의 최대공약수다.

 

 

그리고

최소공배수 = A * B / 최대공약수  이다.

(궁금하다면, 두 수의 최대공약수-최소공배수를 직접 풀어보는 과정을 갖게 되면 알 수 있다.)

 

이를 코드로 짜면

#include <stdio.h>

int x, y;
int G, L; // GCD, LCM

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

int main() {
    scanf("%d %d", &x, &y);
    
    G = gcd(x, y);
    
    L = x * y / G;
    
    printf("%d %d", G, L);
}