1. 최대공약수

결론부터 말하자면 최대공약수를 구하는 알고리즘 코드는 다음과 같다.

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

a % b = r

a와 b가 주어졌을 때, a를 b로 나눈 나머지가 r이다.

그리고, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

gcd(a, b) == gcd(b, a%b)

이 과정을 재귀적으로 반복하다가

a % b == 0 이 되면 그 때의 b 가 a, b 의 최대공약수가 된다. (이건 당연하니까 패스)

(좀 더 간편하게 base case 를 표현하면 한 단 계 더 진행해야겠지만.. if(b == 0) return a;)

왜 a와 b의 최대공약수가 b와 r의 최대공약수와 같을까?

(대소문자 헷갈려서 원래 수를 N ,M으로 변경했다. )

N, M 두 수의 최대공약수를 구해야 하는 상황에서

G를 N, M의 최대공약수라고 가정하면 N와 M는 다음과 같이 표현될 수 있다.

(n와 m는 서로소)

M = m * G;
N = n * G;

M % N = r 의 관계를 다시 표현하면 다음과 같다.