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

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

사용 언어: C++

문제 요약

두 수의 최대공약수와 최소공배수를 출력하라!

풀이

문제는 브론즈 수준이지만, 일단 최대공약수와 최소공배수를 구하는 가장 효율적인 방법을 아는 것은 중요한 법!

유클리드 호제법을 통해 최대공약수(GCD)를 구하고, 이를 이용해 최소공배수(LCM)를 구할 수 있다.

 

유클리드 호제법은 다음과 같다.

두 수 a, b의 GCD는 다음 재귀 공식으로 구한다.

GCD(a, b) = {a            (if b =0)
            {GCD(b, a%b)  otherwise

코드로 표현하면 다음과 같다.

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

그리고 LCM는 GCD를 이용해서 다음과 같이 구할 수 있다.

LCM(a,b) = a * b / GCD(a,b)

 

따라서 종합하면 해당 문제의 코드는 다음과 같다.

#include <iostream>
#include <string>

using namespace std;

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int A, B;
    cin >> A >> B;
    
    int g = gcd(A, B);
    int l = A * B / g;
    
    cout << g << '\n' << l << '\n';

    return 0;
}