최소공배수와 최대공약수 구하기

최소공배수(LCM)란?

최소공배수(LCM)는 두 수의 공통된 배수 중에서 가장 작은 수를 말합니다. 예를 들어, 2와 3의 최소공배수는 6이 됩니다. 6은 2와 3의 배수 중에서 가장 작은 수이기 때문입니다. 이를 수식으로 표현하면 다음과 같습니다.

LCM(a, b) = (a * b) / GCD(a, b)

여기서 GCD는 최대공약수(Greatest Common Divisor)를 의미합니다.

최대공약수(GCD)란?

 

최대공약수(GCD)는 두 수의 공통된 약수 중에서 가장 큰 수를 말합니다. 예를 들어, 12와 18의 최대공약수는 6이 됩니다. 6은 12와 18의 약수 중에서 가장 큰 수이기 때문입니다. 이를 수식으로 표현하면 다음과 같습니다.

GCD(a, b) = GCD(b, a % b)

최대공약수(GCD) 구하는 방법

두 수 a와 b의 최대공약수를 구하기 위해서는 다음과 같은 알고리즘을 사용할 수 있습니다.

1. 두 수 a와 b 중 큰 수를 a에 저장하고, 작은 수를 b에 저장합니다.
2. b가 0이 될 때까지 다음을 반복합니다.
   1. a를 b로 나눈 나머지를 r에 저장합니다.
   2. a에는 b의 값이, b에는 r의 값이 들어가도록 갱신합니다.
3. b가 0이 되면 a가 최대공약수가 됩니다.

최소공배수(LCM) 구하는 방법

 

두 수 a와 b의 최소공배수를 구하기 위해서는 다음과 같은 알고리즘을 사용할 수 있습니다.

LCM(a, b) = (a * b) / GCD(a, b)

즉, 최소공배수는 두 수의 곱을 최대공약수로 나눈 값입니다.

예제로 알아보는 최대공약수(GCD)와 최소공배수(LCM)

다음 예제를 통해 최대공약수와 최소공배수를 구하는 방법을 이해해봅시다.

예제 1: 두 수 24와 36의 최대공약수와 최소공배수를 구해보겠습니다.

해결 방법:

• 먼저, 24와 36 중 큰 수를 36으로 정하고 작은 수를 24로 정합니다.
• 36을 24로 나눈 나머지는 12입니다. (36 % 24 = 12)
• 12를 24로 나눈 나머지는 0입니다. (12 % 24 = 0)
• 나머지가 0이 되었기 때문에 최대공약수는 24가 됩니다.
• 최소공배수는 (24 * 36) / 24 = 36이 됩니다.

따라서, 두 수 24와 36의 최대공약수는 24이고 최소공배수는 36입니다.

마무리

 

최소공배수와 최대공약수는 수학적인 개념이지만 일상적으로 자주 사용되는 개념입니다. 잘 이해하고 활용한다면 다양한 수리 문제를 효과적으로 해결할 수 있을 것입니다. 최소공배수와 최대공약수를 구하는 공식과 알고리즘을 활용하여 만나는 다양한 문제들을 해결해보세요!