유클리드 호제법

유클리드 호제법(Euclidean Algorithm)은

두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 간단하고 효율적인 방법입니다.

유클리드 호제법의 원리

1. 두 숫자 A와 B가 있다고 가정합니다. 여기서 A>B라고 합시다.
2.  .
3. R=0이 될 때까지 A를 B로, B를 R로 반복합니다.
4. 나머지가 0이 되면, 그때의 B가 A와 B의 최대공약수입니다.

간단한 예시

A=56, B=36인 경우를 봅시다.

1. 56÷36=1 (몫), 나머지 20.
   • A=36, B=20로 바꿉니다.
2. 36÷20=1 (몫), 나머지 16.
   • A=20, B=16로 바꿉니다.
3. 20÷16=1 (몫), 나머지 4.
   • A=16, B=4로 바꿉니다.
4. 16÷4=4 (몫), 나머지 0.
   • 나머지가 0이므로, 최대공약수는 4입니다.

유클리드 호제법은 큰 수를 작은 수로 나누고, 나머지를 계속 나누는 방식으로 최대공약수를 구합니다

 

1. 최대공약수(GCD)를 구하는 함수

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b; // 나머지를 구합니다.
    a = b; // 큰 수를 작은 수로 바꿉니다.
    b = r; // 작은 수를 나머지로 바꿉니다.
  }
  return a; // b가 0이 되었을 때, a가 최대공약수입니다.
}

 

2. 최소공배수(LCM)를 구하는 함수

function lcm(a, b) {
  return (a * b) / gcd(a, b); // 두 수를 곱한 값을 GCD로 나누면 LCM입니다.
}

​3. 사용 예시

const num1 = 12;
const num2 = 18;

const gcdResult = gcd(num1, num2);
const lcmResult = lcm(num1, num2);

console.log(`최대공약수(GCD): ${gcdResult}`); // 출력: 최대공약수(GCD): 6
console.log(`최소공배수(LCM): ${lcmResult}`); // 출력: 최소공배수(LCM): 36

코드 설명

1. gcd(a, b) 함수는 유클리드 호제법을 이용하여 최대공약수를 계산합니다.
2. lcm(a, b) 함수는 GCD를 이용해 최소공배수를 계산합니다.
3. 두 함수는 반복문을 사용하여 간단하면서도 효율적으로 작동합니다.