[백준/c++] 2609번 최대공약수와 최소공배수

22609번 문제 링크

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

풀이

최소공배수는 두 값의 곱 / 최대공약수 의 공식으로 구하면 되기 때문에 최대공약수를 구하는 로직만 구현하면 됩니다.

최대공약수를 구하는 방법은 총 두가지가 있는데요.

첫번째, 무차별 대입으로 구하는 방법
두 수 중 작은 수를 선택한 다음 1부터 작은 자연수까지의 모든 수로 두 수를 나누면서 동시에 나누어 떨어지는 가장 큰 수를 구하는 방법

두번째, 유클리드 호제법으로 구하는 방법
x, y 의 최대공약수는 y, r 의 최대공약수와 같다는 원리를 이용하는 방법

여기선 유클리드 호제법을 사용해서 구현해보도록 하겠습니다.

최소공배수, 최대공약수에 대해서 더 자세하게 알고 싶으신 분은 ➡️ 최소공배수, 최대공약수와 유클리드 알고리즘 해당 포스팅을 확인해주세요 🙂

소스코드

#include <iostream>
using namespace std;

int gcd(int x, int y) {
	// 재귀 함수로 최대공약수를 구함 
    // y 가 0 일 때 x 의 값이 최대공약수임 
    if (y == 0) return x;
    return gcd(y, x%y);
}

int main() {
    int x, y;
    cin >> x;
    cin >> y;
    
    int result_gcd = gcd(x,y);
    cout << result_gcd << endl; // 최대 공약수
    cout << x * y / result_gcd; // 최소 공배수 (두 값의 곱 / 최대공약수)
    
    return 0;
}

정답