[C++] 유클리드 호제법 - 최대공약수와 최소공배수 구하기

최대공약수 알고리즘

두 수 a, b (a > b) a 를 b로 나눴을 때,
나누어 떨어진다면 b 가 a, b 의 최대공약수
나누어 떨어지지 않는다면 나누어 떨어질 때까지 b 를 a%b(나머지 r) 로 나누는 과정 반복하기
ex) a = 24, b = 16 일 때, 24 % 16 = 8 이므로 나누어 떨어지지 않기 때문에 r = 8
b 를 r로 나누면 16 % 8 = 0 로 나누어 떨어지기 때문에 최종적으로 최대공약수는 8

이를 코드로 나타내면 재귀함수로 구현해볼 수 있음

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

❗️ 다항식의 경우

int a = 8;
int b = 16;
int c = 24;
	
int result = GCD(a,b); //a와 b의 최대공약수 
result = GCD(result,c); //a와 b의 최대공약수 result와 c의 최대공약수

a, b 에 대한 최대공약수를 구한 후에 c 와의 최대공약수를 구하는 방식으로 적용 가능

최소공배수 알고리즘

int lcm(int a, int b)
{
    return a * b / gcd(a,b);
}

두 수 a, b 를 최대공약수로 나눈 값과 최대공약수를 곱해주면 최소공배수를 구할 수 있음