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

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

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

 

유클리드 호제법

최대공약수를 구한 방법

두 자연수 A, B의 최대공약수를 구할 땐, 유클리드 호제법을 사용한다.

A > B 일때, A를 B로 나눈 나머지를 R이라 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

B > R 이고, A를 R로 나눈 나머지를 R2라 하면, B와 R의 최대공약수는 R과 R2의 최대공약수와 같음을 반복적용한다.

이 과정을 반복하다가, 두 수(C, D(C>D)라 하자)를 나눈 나머지가 0이 되었을 때, 나누는 수 D가 A와 B의 최대공약수가 된다.

 

자세한 내용은 아래 링크를 참고하길.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

최소공배수를 구한 방법

어렸을 적에 다들 다음과 같은 소인수분해를 해봤을 것이다.

나는 여기서 최대공약수 X (A/최대공약수) X (B/최대공약수) = 최소공배수 를 이용하였다.

+나중에서야 깨달았는데, 최소공배수 X 최대공약수 = 두 수의 곱 이었다... 눈치가 좋은 사람이라면 금방 깨달았을 것..ㅎ

 

제출 코드

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int A, B, ans1, ans2;
    cin >> A >> B;
    int a = max(A, B);
    int b = min(A, B);
    while(true){
        int c = a % b;
        if(c == 0){
            ans1 = b;	//최대공약수 구함
            break;
        }else{
            a = b;
            b = c;
        }
    }
    ans2 = ans1 * (A/ans1) * (B/ans1);	//최소공배수 구함
    
    cout << ans1 << '\n' << ans2;
}