최대 공약수, 최소 공배수 계산

최대 공약수와 최소 공배수:

1. 최대 공약수 (GCD: Greatest Common Divisor): 두 개 이상의 정수의 공통된 약수 중에서 가장 큰 수를 의미합니다.
2. 최소 공배수 (LCM: Least Common Multiple): 두 개의 정수의 공통된 배수 중에서 가장 작은 수를 의미합니다.

유클리드 호제법:
두 수 A와 B의 최대 공약수는 A와 B의 나머지와 B의 최대 공약수와 같습니다. 이 원리를 바탕으로 재귀적 혹은 반복적으로 GCD를 계산할 수 있습니다.

[ GCD(A, B) = GCD(B, A % B) ]

자바스크립트로의 구현 예:

// 최대 공약수 (GCD)
function gcd(a, b) {
    if (b === 0) return a;
    return gcd(b, a % b);
}

// 최소 공배수 (LCM)
function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

console.log(gcd(56, 98));  // 출력: 14
console.log(lcm(56, 98));  // 출력: 392

해설:

• 위의 gcd 함수에서는 유클리드 호제법을 이용하여 최대 공약수를 계산합니다. 재귀적으로 gcd(b, a % b)를 호출하여 b가 0이 될 때까지 반복하며, b가 0이 되면 a를 반환합니다.
• lcm 함수에서는 두 수의 곱을 그 두 수의 최대 공약수로 나누어 최소 공배수를 계산합니다. 이는 수학적으로 다음과 같이 표현됩니다: ( LCM(A, B) = \frac{A \times B}{GCD(A, B)} ).

유클리드 호제법은 두 수의 최대 공약수를 빠르게 계산하기 위한 효율적인 방법이며, 이를 활용하면 최소 공배수 또한 쉽게 구할 수 있습니다.