GCD 유클리드 호제법

GCD란? 최대공약수이다.

그러면 최대 공약수란 무엇일까?

두 정수 A와 B를 나누어 떨어지게 하는 수 중 가장 큰 정수

그러면 유클리드 호제법은 무엇일까?

바로 GCD를 쉽게 알아내는 방법이다.

유클리드 호제법

• 이 유클리드 호제법을 통해 GCD(A,B) 구하기 전에 간단한 규칙 몇 가지를 알아야 한다.

1. A=0 일 때, GCD(0,B) = B 이다.
2. B=0 일 때, GCD(0,A) = A 이다.
3. A를 A = B * Q + R의 형식으로 나타낸다면
4. GCD(A,B) = GCD(B,R) 이므로
5. GCD(B,R)을 찾으면 된다.
6. 이때, R이 0이면 B가 GCD이다.
7. R이 0이 아니라면 A에 B 값을 다시 넣고, R을 B에 대입한 후 다시 반복한다.(값을 바꿔서 3부터 다시 반복)

재귀함수로 구현한 유클리드 호제법으로 GCD를 구하는 코드

• 재귀 함수를 사용하면 구현이 간단하며 코드가 간결하고 시간 복잡도가 O(logN)이다.

int uclidGCD(int a, int b) {
	if(a % b == 0) { // R == 0 이면 b를 반환
    	return b;
    }
    return uclidGCD(b, a%b) // R != 0 이므로 반복
}

추가적으로 최대 공배수는 A * B / GCD 이다.
N 개의 정수의 최대 공배수를 구하려면 연속으로 GCD 함수에 넣으면 된다.