[수학] 2609번 최대공약수와 최소공배수 C++ <유클리드 풀이>

이 문제는 최소공배수와 최대공약수를 구하는 문제입니다. 

최대공약수를 구한다음, 주어진 수를 최대공약수로 나눈 뒤 나머지들을 최대공약수와 곱해주면 최소공배수를 구할 수 있습니다. 

그렇다면 최대공약수는 어떻게 구하면 될까요?

유클리드 알고리즘을 이용하면 됩니다. 

유클리드 호제법(=유클리드 알고리즘) 은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나입니다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 의미합니다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 

쉽게 설명하자면, 

1. 큰수를 작은 수로 나눕니다.

2. 나누는 수를 나머지로 계속 나눕니다. 

3. 나머지가 0이 나올 때까지 반복합니다.

4. 나머지가 0이 나온다면 그 때 나누는 수가 최대공약수가 됩니다.

예시를 들어 설명드리겠습니다.

1512와 1008의 최대공약수를 구해봅시다.

우선 1512가 1008보다 크니까 1512를 1008로 나눠줍니다. 그럼 나머지가 504가 나오죠?

그럼 1008을 504로 나눠줍니다. 그럼 나머지가 0으로 떨어지죠

그렇다면 1512와 1008의 최대공약수는 504입니다.

1. 1512%1008=504

2. 1008%504=0

그렇다면 최대공약수는 504

이번엔 1440과 864의 최대공약수를 구해볼까요?

1440을 864로 나눠줍니다. 그럼 나머지는 576이 나오죠

그리고 864를 576으로 또 나눠줍니다.

나머지가 288이 나옵니다.

576을 다시 288로 나눠줍니다. 그럼 나머지가 0이나오죠. 그러면 288이 최대공약수가 됩니다.

1. 1440%864=576

2. 864%576=288

3. 576%288=0

따라서 최대공약수는 288

이해가 되시나요?!

그렇다면 왜 이런 방법이 성립되는지 증명을 해보도록하겠습니다.

그럼 코딩으로 구현해보겠습니다.

#include<iostream>
 
using namespace std;
 
int divide(int x, int y)
{
    if (x % y == 0)
    {
        return y;
    }
    return divide(y, x % y);
}
 
int main()
{
    int A, B;
    int common_max = 0;
    cin >> A >> B;
 
    if (A >= B)
    {
        common_max=divide(A, B);
    }
    else common_max=divide(B, A);
 
    cout << common_max << "\n";
    cout << A * B / common_max << "\n";
}

정답입니다.