[알고리즘] 유클리드 호제법

a,b의 최대공약수는 어떻게 구할 수 있을까요 ? 먼저, 최대공약수는 a,b를 나누었을 때 나머지가 0이 되는 공약수 중 가장 큰 값을 의미합니다. 간단히 생각나는 방법은 a,b중에 작은 값을 min이라고 했을 때 2부터 min까지 값을 하나씩 증가하면서 a,b를 나누었을 때 나머지가 0이 되는 수 중에서 가장 큰 값을 구하면 a,b의 최대공약수를 구할 수 있을 것 같습니다.

 

하지만 min값이 큰 수일때는 그 만큼 반복을 해야 하기 때문에 비효율적입니다.

 

두 수의 최대공약수를 구하는 방법에는 유클리드 호제법이 있는데, 이번 시간에는 이 알고리즘으로 최대공약수를 구하는 방법을 설명하겠습니다. 여기서 r은 a를 b로 나누었을 때, 나머지 값을 의미합니다.

 

a          b      r

48      26    22

26      22    4

22       4     2

4         2     0

 

먼저 a를 b로 나누었을 때의 값은 r로 나누어 줍니다. 그다음 b값을 a에 넣어주고 r값을 b에 넣어주고 r이 0이 될때까지 반복합니다.

반복을 하다, r이 0이되었을 때, b값이 최대공약수가 됩니다.

 

최소공배수는 기존의 두 정수를 곱한 값에 최대공약수를 나누면 구할 수 있습니다.

 

1. while문

#include <iostream>

using namespace std;

int main()
{
    int a = 25;
    int b = 15;
    int r;
    int A = a, B = b;
    int GCD, LCM;

    while (true)
    {
        r = a % b;
        if (r == 0)
        {
            GCD = b;
            break;
        }
        else
        {
            a = b;
            b = r;
        }
    }

    cout << "최대공약수 : " << GCD << "\n";
    cout << "최소공배수 : " << (A * B) / GCD;
    return 0;
}

 

2. 재귀

#include <iostream>

using namespace std;

int gcd(int big, int small)
{
    if (small > big)
    {
        int temp;
        temp = big;
        big = small;
        small = big;
    }
    if (big % small == 0)
    {
        return small;
    }
    return gcd(small, big % small);
}
int main()
{
    int a = 25;
    int b = 15;
    int GCD = gcd(a, b);

    cout << "최대공약수 : " << GCD << "\n";
    cout << "최소공배수 : " << (a * b) / GCD;
    return 0;
}