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

https://www.acmicpc.net/problem/2609

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

 

최대공약수는 유클리드 호제법을 사용하여 쉽게 구할 수 있다. 유클리드 호제법은 아래와 같다.

​

a, b 두 수가 있다. 이때 a는 항상 b보다 커야한다.

a % b = c

b % c = d

c % d = 0

이면 a, b의 최대공약수는 d다.

​

재귀 함수로 간단하게 구현할 수 있다. 최소공배수는 두 수의 곱에 최대공약수를 나눠주면 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int x, int y){
    if(x % y == 0)
        return y;
    return gcd(y, x % y);
}

int main(){
    int x, y;
    cin >> x >> y;
    
    if(x < y)
        swap(x, y);
    
    int g = gcd(x, y);
    
    cout << g << endl << x * y / g << endl;
    return 0;
}