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

문제 - 최대공약수와 최소공배수 (Bronze 1)

[백준 2609] https://www.acmicpc.net/problem/2609

이 문제는 최대공약수와 최소공배수를 구하는 간단한 수학문제이다.
최대공약수를 재귀를 사용해서 구한 뒤, 두 숫자 a,b의 곱을 최대공약수로 나눈 수가 최소공배수임을 이용해서 구현할 것이다.

풀이 전략

• 최대 공약수 - 재귀를 이용하여 구현
  (나머지가 0이 될 때까지 반복)
• 최소공배수 = a * b / 최대 공약수

소스코드

#include <iostream>
using namespace std;

int gcd(int a, int b){
    if(b==0)
        return a; // b==0이면 a가 최대 공약수
    else
        return gcd(b,a%b); // b!=0이면 a%b가 0이 될때까지 재귀 반복
}
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a,b;
    cin>>a>>b;

    cout<<gcd(a,b)<<" "<<a*b/gcd(a,b)<<endl;
    return 0;
}

결과

결론

재귀를 이용하여 최대 공약수를 구하는 공식과 두 입력값을 곱한 값을 최대공약수로 나눈 값이 최소공약수 임을 알고 있다면 쉽게 풀 수 있는 문제이다.

관련 문제

[백준 1850 - 최대 공약수] https://www.acmicpc.net/problem/1850