[Algorithm] 최대공약수, 최소공배수

⚪최대공약수

최대공약수 GCD(Greatest Common Divisor)는 두 자연수가 공통으로 갖는 약수들 중 가장 큰 값

이를 구하는 알고리즘중 하나로 유클리드 호제법(Euclidean Algorithm)이 존재한다

🔹유클리드 호제법

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

a가 24, b가 18 이라고 해보자.

	GCD	a	b	a%b
1회	GCD(24, 18)	24	18	6
2회	GCD(18, 6)	18	6	0

2번째 시도만에 나머지가 0으로 떨어졌으며, 이때 나누는 수(6) 이 최대공약수가 된다.

🔹코드

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

⚪최소공배수

최소공배수 LCM(Least Common Multiple)은 두 자연수들의 배수들 중에서 공통된 가장 작은수

최소공배수 = 두 자연수의 곱 / 최대공약수

🔹코드

int LCM(int a, int b)
{
    return a * b / GCD(a, b);
}