gcd

함수명

gcd  최대공약수를 산출한다

형식

int gcd(int n1, int n2);

인수

n1, n2  2개의 부가 아닌 정수

함수치

2개의 정수의 최대공약수

주의 사항

용례(gcd-test.c )

gcd(1996, 2000);

프로그램(gcd.c )

int gcd(int n1, int n2)
{
    if (n2 == 0) return n1;
    else return gcd(n2, n1 % n2);
}

설명

최대공약수를 요구하는 방법은, 2 천년 이전의 고대 그리스 사람에 따라 달라 발견되어 Euclid의 저서 「Elements」에 자세하게 쓰여져 있어 Euclid의 알고리즘이라고 하고 있다.

Lame의 정리에 의해, 이 알고리즘은 정수의 작은 (분)편의 자리수의 5배 이내에서 반드시 종료한다. 따라서 계산량은 O(logN)이다.

또, n개수의 최대공약수를 요구하려면 , 우선 최초 2개의 정수에 상기의 방법을 적용해 최대공약수를 요구해 다음에 3번째의 정수로 계산한 최대 공약수로부터 다시 최대공약수를 계산한다. 이와 같이 마지막 정수까지 조] 돌려주면, n개의 정수의 최대공약수가 요구된다.

관련 함수