최대공약수와 최소공배수

최대공약수

흔히 최대공약수는 줄여서 GCD라고 쓰며 두 수의 약수 중 가장 큰것을 일컫는 말이다.

최대공약수를 구하기 위해 가장 많이 쓰는 방법은 유클리드 호제법이다.

두 정수 a,b 그리고 a를 b로 나눈 나머지가 r이라고 할 때

a와 b의 최대공배수는 b와 r의 최대공배수와 같다는 것이다.

즉 이런식으로 동작하며 두 수를 나눈 나머지가 0이 됐을 때 알고리즘이 끝나게 된다.

결과적으로 위의 그림 기준으로는 3이 최대공배수가 된다.

재귀를 사용해 다음의 과정을 코드로 나타내보면 다음과 같다.

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

재귀없이 보다 직관적으로 코드를 작성해보면 다음과 같다.

int gcd(int a, int b) {
	while (b != 0) {
		int r = a%b;
		a = b;
		b = r;
	}
	return a;
}

최소공배수

최소공배수는 줄여서 LCM이라고 하며

두 수 A,B가 있을 떄 LCM * GCD = A * B 이기 때문에 이 식을

LCM = A * B / GCD 로 바꾸면 쉽게 코드로 구현할 수 있다.