TIL - 최대공약수 코드

최대공약수 구하기

최대 공약수를 구할 때는 유클리드 호제법을 사용한다고 한다.

유클리드 호제법

• 유클리드 알고리즘이라고도 불림
• 2개의 자연수 혹은 정식의 최대공약수를 구하는 알고리즘
• 두 수가 서로의 수를 나누어 원하는 수를 얻는 알고리즘을 의미
• 인류 최초의 알고리즘이라고도 함 (오오..)

유클리드 호제법의 증명

G를 A와 B의 최대공약수 라고 할 때, A = aG, B = bG 로 나타낼 수 있다.
A = Bq + r 이라고 한다면, aG = bGq + r 로 나타낼 수 있다.
정리하면 r = aG - bGq = (a-bq)G 이다.
B = bG, r = (a-bq)G 이므로
G가 B와 r의 최대 공약수가 되기 위해서는 b와 (a-bq)가 서로소임을 증명해야 한다.

만약 서로소가 아니라면,
b = mg, a-bq = ng 로 나타낼 수 있고, 이 때 g라는 공약수가 존재한다.
b 값을 오른쪽의 식에 대입하면 a-mgq = ng
정리하면 a = (mq+n)g 이다.

처음에 A와 B 두 수를 A = aG, B = bG 로 선언했는데,
이는 a와 b가 서로소라는 의미이다.
하지만 위의 식에서 b = mg 이고, a = (mq+n)g 라면 a와 b는 공약수 g를 갖게 된다.
따라서 b 와 (a-bq)는 서로소이다.

참고: https://arinnh.tistory.com/74

유클리드 호제법을 사용한 최대공약수를 구하는 코드

public int gcd (int num1, int num2) {
	// 만약 num1을 num2로 나눴을 때의 나머지가 0이라면
    if (num1 % num2 == 0) {
    	// 최대공약수는 num2
    	return num2;
    }
    // 그렇지 않다면 num2를 num1을 num2로 나눴을 때의 나머지로 다시 구함
    return gcd(num2, num1 % num2);
}