최대공약수 알고리즘, 유클리드의 호제법 +최소공배수 구하기

 

1. 유클리드 호제법이란

• 두 자연수의 최대공약수를 구하는 알고리즘 중 하나
• 유클리드의 저서 《기하학원본》에 기재되어 있는 최대공약수를 구하는 방법
• 호제법 또는 연제법 이라고 한다

 

사용되는 성질

a를 b로 나눈 나머지 = c 이면

a, b의 최대공약수는 b, c의 최대공약수와 같다

 

 

알고리즘

두 자연수 또는 다항식 a,b의 최대공약수를 구하는 데 있어,

자연수일 때는 a > b,

다항식일 때는 a의 차수가 b의 차수 이상이라 하고,

다음과 같이 나눗셈을 실행한다

 

b를 c로 나눈 나머지 = c' 를 구하고

c'를 d로 나눈 나머지 = ...

위 과정을 반복하여 나머지가 0이 되었을 때의 '나누는 수'가 a와 b의 최대공약수이다.

 

 

 

2. 예시

78696과 19332의 최대공약수 구하기

     78696＝19332×4＋1368

     19332＝1368×14＋180

     1368＝180×7＋108

     180 = 108 x 1 + 72     

     108 ＝72×1＋36

     72 ＝36×2

 

 

 

3. C# 코드 예시

1. 재귀함수 사용

//GCD - Greatest Common Divisor
public int GCD(int a, int b)
{
    if(b == 0) 
        return a;
    else
        return GCD(b, a % b);
}

2. 반복문 사용

public int GCD(int a, int b)
{
    int remainder = 0;
    
    while(true)
    {    
         remainder = a % b;
         
         if(remainder == 0)
             break;
             
         a = b;
         b = remainder;
    }
    
    return b;
}

 

 

 

4. 최소공배수 구하기

최대공약수 구하는 법을 알기때문에 최소공배수는 쉽게 구할 수 있다

 

• a와 b의 최소공배수 = a와 b의 곱을 a와 b의 최대공약수로 나눈 것과 같다

 

따라서 최소공배수를 구하는 법은 다음과 같다

//LCM - Least Common Multiple
public int LCM(int a, int b)
{
    return (a * b) / GCD(a, b);
}