유클리드 호제법(GCD)

유클리드 호제법 은 최대공약수, 최소공배수를 구하는 외워두면 편리한 공식(?) 과도 같은 알고리즘이다.

자세한 설명은 https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

위키를 보면 이해할 수 있지만,

간단하게 설명하자면 A라는 숫자와 B 라는 숫자가 있을 때, 한 숫자를 다른 숫자로 모듈러 연산(%) 하다보면 한 숫자가 0이 되는 경우가 발생하고

이때의 다른 숫자가 A,B의 최대공약수가 된다.

 예시로 (88,42) -> (42, 4) -> (4, 2) -> (2, 0) 이때 2가 최대공약수. (88과 42의 최대공약수는 2)

<소스코드>

#include <cstdio>

int gcd(int a, int b) {
	return a%b ? gcd(b, a%b) : b;
}

이 때, 반환되는 return 값이 초기 두 숫자의 최대공약수가 되고 A*B/gcd(A,B) 가 최소공배수가 되는 것이다.