Algorithm - 유클리드 호제법

유클리드 호제법 ( Euclidean algorithm )

 

두 정수 A, B의 최대공약수를 구하는 알고리즘입니다.

 

원리

 

두 정수 a, b가 주어졌을때, a를 b로 나눈 나머지를 r이라고 하자.

a, b의 최대공약수를 (a, b)라고 하면, 다음이 성립한다.

 

(a, b) = (b, r)

 

ex)

 

(1071, 1029) = (1029, 42) = (42, 21) = (21, 0) = 21

 

코드

 

public int gcd(int p, int q) {
    if (q == 0) return p;
    return gcd(q, p % q);
}

 

팁 : 큰 숫자를 첫 번째 인자로 주어야 불필요한 재귀 1번을 아낄 수 있다.