최초의 알고리즘은 무엇일까?

최초의 알고리즘은 무엇일까?

유클리드 호제법이다. (기원전 300년경)

유클리드 호제법은 어디에 쓰는 알고리즘일까?

최대공약수를 구하기 위해 사용한다.

들어가기에 앞서, 호제법이란?
"두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘"

실제 내용은 생각보다 훨씬 간단하다.

1)    a를 b로 나누고 그 나머지(r)를 구한다. 
2-1)  r 이 0 이라면 ? b가 최대공약수
2-2)  r 이 0 이 아니라면 ? a 자리에는 b를 놓고, b 자리에 r을 넣는다.
다시 1로 돌아간다.

자세한 설명은 재미없으니 생략하도록 하겠다.

코드로 적어보자면 다음과 같다.

#include <stdio.h>

int main()
{
    int a,b;
    scanf("%d %d", &a, &b);

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

    }
    printf("%d", a);
    return 0;
}

최대 공약수 구하기