백준 2609번 최대공약수와 최소공배수(C++)

문제 해결 방안 : 유클리드 호제법을 이용해서 최대공약수를 구현하고 최소공배수는 최대공약수의 수학적 관계를 이용해서 구했다.

 

문제 해결 소감 : 단순한 반복문으로는 답이 없을 것 같고 이미 두 가지 수를 구하는 좋은 방법이 있을 것 같다. 이를 학습한 후 풀었다. 유클리드 호제법이라는 좋은 알고리즘이 있었다. 해당 알고리즘을 학습하는 좋은 기회가 되었다.

#include <iostream>
int A, B;
int Gcd(int a, int b)
{
    if (b == 0)
        return a;
    return Gcd(b, a % b);
}
int Lcm(int a, int b)
{
    return (a * b) / Gcd(a, b);
}
int main(void)
{
    std::cin >> A >> B;
    std::cout << Gcd(A, B) << '\n'
              << Lcm(A, B);
    return 0;
}