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

최대 공약수와 최소공배수를 구해서 제출하면 되는 문제이다.

소인수분해로 풀었지만 다른 풀이를 보던도중 유클리드 호제법을 발견하여 유클리드 호제법으로 한번 더 풀어보았다.

깔끔하게 유클리드 호제법 함수

#include <iostream>

using namespace std;

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

int main()
{
    int a, b;
    cin >> a >> b;

    int gcd = getGCD(a, b); // 최대공약수 : 유클리드 호제법 사용
    int lcm = a*b/gcd;      // 최소공배수 : gcd x lcm = A x B 이용

    cout << gcd << endl;
    cout << lcm << endl;
}

ldgeao99.tistory.com/296