유클리드 알고리즘 (Euclid’s algorithm)

유클리드 알고리즘 (혹은 유클리드 호제법)이란?

두 양의 정수 A, B에 대한 최대공약수를 구하는 알고리즘이다.

이는 O(log N) 으로 가장 효율적으로 GCD를 구한다.

 

* 최대공약수(Greatest common divisor, GCD)란, A, B를 나누는 자연수 중에서 가장 큰 자연수를 말한다.

* 호제법이란, 두 수가 서로 상대의 수를 나누어 원하는 수를 얻는 알고리즘을 말한다.

 

최대공약수는 다음과 같은 성질을 갖는다.

최대공약수의 성질

식에서 mod는 나머지를 구하는 모듈러 연산(%) 이다.

성질을 이용한 예시는 다음과 같다.

 

 

다음은 C++로 구현한 코드이다.

int gcd(int a, int b) {
    if (b > 0) return gcd(b, a % b);
    return a;
}