C2007. 5. 30. 22:35
 

/*
 * -------------------------
 *     유클리드 호제법     *
 * -------------------------
 */

 

#include <stdio.h>

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

    printf("두 정수를 입력하세요. : ");
    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;
}

 

 

// 실행결과

    두 정수를 입력하시오 : 128 72

    최대공약수 = 8

 

// 기계적인  반복으로 최대공약수를 구하는 방법인 컴퓨터 지향 알고리즘으로는

유클리드(Euclid)호제법이 있다. 알고리즘을 간단히 정리하면 다음과 같다.

    

     1. m과 n이 같지 않으면 다음을 반복한다.

    2. m>n이면 m-n, 그렇지 않으면 n=n-m이다.

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

Posted by 타망

댓글을 달아 주세요