[BOJ] 13241 - 최소공배수 (C++)

문제

최소공배수

코드

#include <iostream>

using namespace std;

long long A, B;

int GCD(long long a, long long b){
    return b == 0 ? a : GCD(b, a%b);
}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> A >> B;

    cout << A*B/GCD(A,B);
    return 0;
}

접근

최소공배수를 구하기 위해서 최대공약수 gcd를 먼저 구하였다. 이는 유클리드 호제법을 이용하여 재귀함수를 통해 구할 수 있었다. 또한 최대공약수를 아는 상태에서는 최소공배수 lcm는 a*b/gcd(a,b) 와 같기 때문에 쉽게 구할 수 있었다.

https://ko.wikipedia.org/wiki/최소공배수