[Baekjoon] 2609번: 최대공약수와 최소공배수

✏️ 최대공약수(GCD)

두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

• 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법
• 하지만 유클리드 호제법을 이용하면 빠르게 구할 수 있다.

유클리드 호제법

• a를 b로 나눈 나머지를 r이라고 했을 때 GCD(a,b) = GCD(b,r)과 같다.
• r이 0이면 그 때 b가 최대 공약수이다.
• ex) GCD(24,16) = GCD(16,8) = GCD(8,0) = 8

✏️ 최소공배수(LCM)

두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수이다.
=> 두 수의 최대공약수를 g라고 했을 때, 최소 공배수 l=(a*b)/g 이다.

문제

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

입력

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

출력

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

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cstdio>
using namespace std;
int gcd(int a, int b){
    while(b!=0) {
    	int r = a%b;
    	a = b;
    	b = r;
    }
    return a;
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;
    int res;
    res = gcd(n, m);
    int lcm;
    lcm = n*m/res;
    
    cout << res << '\n' << lcm << '\n';
    
    return 0;
}