유클리드 호제법을 활용하여 최대공약수, 최소공배수 구하기

목차

---

유클리드 호제법 (Euclidean Algorithm)

: 두 자연수의 최대공약수를 구하는 알고리즘. 이때 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.

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

 

- 반복문을 활용한 코드 (C#)

// a > b
int GCD(int a, int b)
{
    while (b != 0)
    {
        int temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

 

- 재귀함수를 활용한 코드 (C#)

// a > b
int GCD(int a, int b)
{
    if (b == 0)
        return a;
    
    return GCD(b, a % b);
}

 

※ 참고 문서 - 위키백과

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

 

최대공약수(GCD)를 활용하여 최소공배수(LCM) 구하기

: 최소공배수(Least Common Multiple)는 최대공약수(Greatest Common Divisor)를 활용하여 아래 식으로 바로 구할 수 있다.

 

→ 최소공배수 = 두 자연수의 곱 / 최대공약수