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

https://www.acmicpc.net/problem/2609

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

두 수 a와 b(a > b)에 대해, 두 수가 최대공약수 n을 가지고 있다고 하자.

두 수가 같은 약수를 가지고 있으므로 a와 b는 각각 서로소 p와 q에 대해 pn과 qn으로 나타낼 수 있는데, a % b = pn % qn = (p % q)n이므로 pn과 qn의 최대공약수는 qn과 (p % q)n의 최대공약수이다.

이 과정을 p와 q 둘 중 하나가 0이 될 때까지 진행하면 나머지 하나가 1이 되므로, 즉 a와 b가 n과 0이 되므로 최대공약수 n을 반환해 최대공약수를 구할 수 있다.

최소공배수는 a * b / n이므로 n과 a * b / n을 차례로 출력한다

#include <cstdio>

// 유클리드 호제법을 이용해 a와 b의 최대공약수를 계산
int gcd(int a, int b) {
    if (!b) return a;
    return ((a > b) ? gcd(b, a % b) : gcd(a, b % a));
}

int main() {
    // a, b: 입력받을 두 수, c: a와 b의 최대공약수
    int a, b, c;

    // a와 b를 입력받은 뒤 최대공약수를 c에 저장
    scanf("%d %d", &a, &b);
    c = gcd(a, b);
    // 최소공배수는 두 수의 곱에 최대공약수를 나눈 값이므로
    // 최대공약수 c와 최소공배수 a * b / c를 출력
    printf("%d\n%d\n", c, a * b / c);

    return 0;
}