C# 유클리드 호제법

 

유크리드 호제법

 

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘

 

a > b 보다 크다는 가정하에 a와 b의 나머지를 r이라 할때 a 와 b의 최대공약수와  b 와 r의 최대공약수는 같다.

 

따라서 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다

 

결론은 재귀로 구한다고 할때

 

두 정수 int a int b가 있고

 

a % b 가 나누어 떨어지면 최대공약수는 a인것이고

나누어 떨어지지 않는다면 b , a % b 를 다시 호출한다.

 

재귀를 이용한 코드

 static int Gcd(int a, int b)
        {
            if (b == 0)
            {
                return a;
            }
            else
            {
                return Gcd(b, a % b);
            }
        }

 

 

비재귀를 이용한 코드

 

 static int Gcd(int a, int b)
        {      
           while(b != 0)
           {
                int c = b;

                b = a % b;
                a = c;
           }

            return a;
        }

 

 

하지만 최대 공약수를 구하고 싶을때 두가지의 자연수가 아닌 2개이상에 자연수들의 최대 공약수를 구해야 할때가 있을것이다.

 

그러면 Gcd_array함수를 만들어 매개변수는 자연수들의 요소가 담겨져있는 배열, 현재 인덱스, 인덱스 크기를 보내주고

 

현재 크기가 1이면 return 현재 인덱스

2면 Gcd 함수에 현재 인덱스와 다음인덱스의 최대공약수를 구하고

3이상이면 Gcd(자신의 인덱스, GCD_Array(현재 배열, 다음 인덱스, 크기 - 1)을 재귀 호출해서 마지막 인덱스 요소까지 접근해 2번째 인덱스 까지의 최대공약수를 구하고 첫번째 요소와 다시 최대공약수를 구하면 그 배열의 최대공약수를 구할수있다.

 

 

  static int Gcd_Array(int[] a, int start, int n)
        {
             
            if (n == 1)
            {
                return a[start];
            }
            else if (n == 2)
            {
                return Gcd(a[start], a[start + 1]);
            }
            else
            {
                return Gcd(a[start], Gcd_Array(a, start + 1, n - 1));
            }
        }

 

 

20, 32, 48, 60 의 최대공약수는 4인데 이 요소들을 담은 배열을 출력하면

 

 

잘 출력되는걸 볼수있다.