유클리드 호제법이란?

유클리드 호제법은 두 정수 m, n의 최대 공약수를 구하는 알고리즘이다.

유클리드 호제법은 재귀함수의 형태로 진행된다.

서로 호(互), 덜다/나누다 제(除)
'호제법'은 두 수가 서로를 나누어서 원하는 값을 얻어내는 방법을 뜻한다.

진행 방식

두 정수 m,n의 최대 공약수 표기 방법은 GCD(m, n)이다.

최대 공약수에는 다음과 같은 성질이 있다.

m을 n으로 나눈 나머지 r은 GCD(m, n) = GCD(n, r)을 만족한다.

알고리즘 진행 방식

1. m을 n으로 나눈 나머지는 r이다.

2. r이 0일 때 n이 최대 공약수가 된다.

3. r이 0이 아닐 때 m에는 n을, n에는 r을 대입하고 다시 1번으로 돌아간다.

예시) m = 51, n = 15
1. 51을 15로 나눈 나머지는 6이다. / m = 15, n = 6
2. 15를 6으로 나눈 나머지는 3이다. / m = 6, n = 3
3. 6을 3으로 나눈 나머지는 0이다.

3이 51과 15의 최대 공약수가 된다.

구현

C++

#include <iostream>
using namespace std;

int GCD(int m, int n)
{
    if (n == 0)
        return m;

    return GCD(n, m%n);
}

int main()
{
    cout << "GCD(51, 15) : " << GCD(51, 15)<< endl;
    cout << "GCD(15, 51) : " << GCD(15, 51)<< endl;
}

1. GCD(51, 15) => n이 15이므로 GCD(15, 6)을 호출
2. GCD(15, 6) => n이 6이므로 GCD(6, 3)을 호출
3. GCD(6, 3) => n이 3이므로 GCD(3, 0)을 호출
4. GCD(3, 0) => n이 0이므로 m인 3을 리턴

C#

static int GCD(int m, int n)
{
    if (n == 0)
        return m;

    return GCD(n, m % n);
}

static void Main(string[] args)
{
    Console.WriteLine($"GCD(51, 15) : {GCD(51, 15)}");
    Console.WriteLine($"GCD(15, 51) : {GCD(15, 51)}");
}

써놓고 보니까 두 언어가 다를 것이 없다. ㅋㅋ

---

참고 자료
오츠키 켄스케 , 『문제 해결력을 높이는 알고리즘과 자료구조, 서수환 옮김, 길벗(2022)
유클리드 호제법 - 위키백과