[C-알고리즘] 유클리드 호제법

※ 최대 공약수 : 공통으로 가지고 있는 약수 중 가장 큰 수

큰 수를 작은 수로 나눠 나머지가 0이 될 때까지 반복하여 최대 공약수를 구할 때 

유클리드 호제법을 이용한다.

                                                                                                              

   <공식>

※ 나머지 구하는 방법

                           

   ▷ BIG : 큰 수 , SMALL : 작은 수

  

① MOK = BIG / SMALL   // 먼저 몫을 구한다.

    NMG = BIG - MOK * SMALL  //  큰 수에서 [ 몫 * 작은 수 ]를 한 값이 나머지다. 

② NMG = BIG % SMALL  // MOD 연산자를 통해 나머지를 구한다.(권장)

#include <stdio.h>
 
int main()
{     
 int A,B, NMG = 1,
     BIG , SMALL , GCM;
     
 printf("정수 2개를 입력하세요\n:");
 scanf("%d %d",&A,&B);
 
  
 if ( A > B)    
 {            // 큰 수에서 작은 수를 나누기 위해서 BIG/SMALL을 정한다 
  BIG = A;
  SMALL = B;
 } else {
  BIG = B;
  SMALL = A;
 }
 
 
 while( NMG != 0 )  // 나머지(NMG)가 0이 될 때까지 반복한다 
 {    
  NMG = BIG % SMALL;   
  BIG = SMALL;         
  SMALL = NMG;    
 }
  
 
  printf("GCM : %d\n",BIG);
}

        

< 입력 : 12 , 5 >

BIG = 12 , SMALL = 5

---

12 % 5  → 나머지(NMG) = 2

BIG = SMALL  

SMALL = NMG

---

5 % 2  → 나머지(NMG) = 1

BIG = SMALL

SMALL = NMG

---

2 % 1  → 나머지(NMG) = 0

BIG = SMALL

SMALL = NMG

---

< 답 : 1 >