유클리드 호제법을 이용한 최대공약수, 최소공배수 계산

유클리드 호제법 : 기원전 300년경 기하학자 유클리드가 주장하여 그의 이름을 딴 공식으로 알려져 있다.
두 자연수 A,B에 대하여 A를 B로 나누었을 때 몫을 Q, 나머지를 R이라고 하면(A = BQ+R)
A,B의 최대공약수는 B,R의 최대공약수와 같다.
<증명> A,B 둘의 최대공약수 G
A = aG, B = bG (a,b는 서로소)
(A = BQ+R, B = bG 이므로)
bGQ+R = aG
=> R = (a - bQ)G
--------------------------
A = aG
B = bG
R = (a-bQ)G
그러므로 A,B의 최대공약수와 B,R의 최대공약수는 G로 서로 같다.

========================================================================
#include <stdio.h>
unsigned int gcd(unsigned int valuer1, unsigned int value2);
unsigned int lcm(unsigned int value1, unsigned int value2);

int main()
{
    unsigned int value1, value2;
    printf("자연수 2개를 입력하시오 : ");
    scanf("%d %d", &value1, &value2);
    printf("최대공약수 : %d\n", gcd(value1, value2));
    printf("최소공배수 : %d\n", lcm(value1, value2));
    return 0;
}

int gcd(int value1, int value2)
{
    int temp;
   
    while(value2 != 0)
    {
        //swap
        temp = value1%value2;
        value1 = value2;
        value2 = temp;
    }
    return value1;
}

int gcd(int value1, int value2)
{
        if(value2 == 0)
                return value1;
        else
                return gcd(value2, value1%value2);
}

int lcm(int value1, int value2)
{
        int temp;
        temp = gcd(number1, number2);
        return (number1/temp)*number2;
}

======================================================================
위의 소스는 우선 돌아가는 것 같지만 약점이 있다.
입력값을 전혀 체크하지 않는다는 것! 만약 자연수를 입력하지 않는다면 문제가 발생할 가능성이 크다.
0 0을 입력한다면? 만약 수를 입력하지 않고 문자를 입력해 버린다면?
간단히 오류체크를 추가해서 main을 바꿔보자.

int main()
{
    unsigned int value1, value2;
    do{
        printf("자연수 2개를 입력하시오 : ");
        scanf("%d %d", &value1, &value2);
    }while(value1 <= 0 || value2 <= 0);
    printf("최대공약수 : %d\n", gcd(value1, value2));
    printf("최소공배수 : %d\n", lcm(value1, value2));
    return 0;
}

간단히 do-while을 사용해서 자연수가 아닌 정수(0,음수)는 걸러주도록 했다.
숫자 이외의 값이 입력되는 경우는 찾아보기 쉽게 다른 글로 다시 써야겠다.