프로그래밍 도전 #1 – 유클리드 호제법

‘유클리드 호제법’에 대한 위키백과 문서를 참고하여 두 수 간의 최대공약수(GCD)를 구하는 코드를 작성해보았다.

초등/중등 교육과정에서 배운 방법을 코드로 옮기는 방법도 있지만 식상(?)하므로, 유클리드 호제법(Euclidean algorithm)에 대한 설명을 보고 코드로 옮겼다.

재귀(recursion)를 사용하는 방법도 있겠으니 나도 나중에 해봐야겠다.

#include <stdio.h>

int getGCDe(int a, int b)
{
    int r;

    while(r != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    int a, b;
    int temp;

    // Inputs
    printf("a and b: ");
    scanf("%d %d", &a, &b);

    // Swap `a` and `b` if `b` is bigger
    if(a < b)
    {
        temp = a;
        a = b;
        b = temp;
    }

    printf("%d \n", getGCDe(a, b));

    return 0;
}

Leave a Reply