최대 공약수(Greatest Common Divisor)

최대 공약수란?

2개 이상의 수의 공약수 중 가장 큰 수

10의 약수 : 1, 2, 5, 10

15의 약수 : 1, 3, 5, 15

10과 15의 공약수 : 1, 5

10과 15의 최대 공약수 = 5

• 수학 공식없이 반복문으로 찾는 방법
  

1부터 반복문으로 두 수 모두를 나눌 수 있는 수를 검색

반복은 입력된 수 중 작은 숫자까지만

//최대 공약수

int Algorithm::GreatestCommonDivisor(int num01, int num02)

{

        //방법01

        int max = 1;    //공약수 저장 변수

        int length = num01 < num02 ? num01 : num02;      //작은 숫자 만큼만 반복 수행

 

        for (int i = 1; i <= length; i++)

        {

               //두 수 모두 나누어떨어지면 max대체

               if ((num01 % i == 0) && (num02 % i == 0))

               {

                       max = i;

               }

        }

 

        return max;

}

• 유클리드 호제법을 활용하여 찾는 방법
  

유클리드 호제법(Euclidean algorithm)

두 정수 혹은 두 다항식의 최대 공약수를 구하는 알고리즘

정수 : X, Y (X ≠ 0, Y ≠ 0, X > Y)

나머지 : Z (X를 Y로 나눴을때 나머지)

최대 공약수 : f(X, Y)

라고 하면

f(X, Y) = f(Y, Z)

라고 할 수 있다는 것이 유클리드 호제법이다.

공식으로 보면, 이해하기 어렵지만 숫자로 보면 쉽게 이해가 된다.

예를 들어

X = 1480, Y = 540 이라고 하자

1480 = 540 x 2 + 400

540 = 400 x 1 + 140

400 = 140 x 1 + 120

140 = 120 x 1 + 20

120 = 20 x 6 + 0

나머지가 0이 되는 20이 최대 공약수이다.

f(x, y)식으로 적어보면 이렇다.

f(1480, 540) = f(540, 400) = f(400, 140) = f(140, 120) = f(120, 20) = 20

-재귀함수 이용

//유클리드 호제법_재귀 함수

int Algorithm::GreatestCommonDivisor(int num01, int num02)

{

        if (num02 == 0)

               return num01;

 

        GreatestCommonDivisor(num02, num01 % num02);

}

-반복문 이용

 //유클리드 호제법_반복문

int Algorithm::GreatestCommonDivisor(int num01, int num02)

{

       

        int remainder;

        while (num02)

        {

               remainder = num01 % num02;

               num01 = num02;                

               num02 = remainder;

        }

 

        return num01;

}