최대 공약수 구하기

 

유클리드 호제법

 

1. 두 정수 m, n(m>n)이 있을 때, m과 n의 최대공약수는 m-n과 n의 최대공약수와 같다.

 

      ⓐm과 n이 틀리면 다음을 반복한다.     

            ⓑm>n이면 m=m-n, 아니면 n=n-m이다.

      ⓒm또는 n이 구하고자 하는 최대공약수이다.

 

 

#include <stdio.h>

int main(void)
{
       int a, b, m, n;

       printf("Insert 2 numbers: ");
       scanf("%d %d" , &a, &b);

       m = a; n=b;

       while(m!=n){
        if(m>n)
               m= m-n;
        else
               n=n-m;

       }

       printf("최대공약수 : %d\n", m);

       return 0;

}

 

 

2. m과 n의 차이가 클 경우 뺄셈(m-n) 대신에 나머지(m%n)을 이용하는 방법

 

#include <stdio.h>

int main(void)
{
        int a, b, m,n,k;
        printf("두 정수를 입력하시오. : ");
        scanf("%d %d", &a, &b);

        m=a; n=b;

        do{
                k = m%n;
                m = n; n = k;
        }while(k!=0);

        printf("최대공약수 = %d\n", m);
        return 0;
}