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

문제

백준 2609 문제 보기

접근 방법

유클리드 호제법을 사용하여 최대공약수를 구하고 입력된 두 수의 곱에 다시 최대공약수로 나누어 최소 공배수를 구한다.

코드

#include <iostream>

using namespace std;

int N, M;
int gcd, lcm;

int getGCD(int a, int b) {
    return b ? getGCD(b, a%b) : a;
}

int main() {

    cin >> N >> M;

    gcd = getGCD(N, M);
    lcm = (N * M) / gcd;

    cout << gcd << endl;
    cout << lcm << endl;
    return 0;
}