최대공약수와 최소공배수

이번 포스트에서는 최대공약수와 최대공배수에 대해서 알아보겠습니다.

---

1. 최대공약수란?

최대 공약수 (Greatest Common Divisor)란 두 수, 혹은 그 이상의 여러 수의 공통인 약수 (공약수) 중 가장 큰수를 의미 하며 수학 기호로  $ GCM(a,b) $와 같이 표현 합니다.

만일 $ GCD(a,b) = 1 $인 경우 두 수 a, b는 서로소 (Relatively prime, Coprime)라고 합니다.

---

2. 최대공약수 구하기

• 2부터 $ min(a, b) $ 까지 모든 정수로 나누어 보기

function getGCD(a, b) {
    const large = a > b ? a : b;
    const small = a > b ? a : b;
    let gcd = 1;
    for (let i = 2; i <= small; i++) {
        if (large % i === 0 && small % i === 0) {
            gcd = i;
        }
    }
    return gcd;
}

• 유클리드 호제법 (Euclidean algorithm)

 

$ a\;mod\;b = r \quad(a \geq b)$ 일 때 

$ GCD(a, b) = GCD(b, r) $ 이 성립한다.

function getGCD(a, b) {
    if(b === 0) {
        return a;
    }
    let r = a % b;
    return getGCD(b, r)
}

 

---

 

3. 두 개 이상의 수들의 최대공약수

여러 수의 최대 공약수는 두 개씩 짝지어 순차적으로 최대공약수를 구해 나가면 됩니다.

$ GCD(a,b,c) = GCD(a, GCD(b, c)) $

 

---

 

4. 최소공배수란?

최소공배수 (Least Common Multiple)란 두 수, 혹은 그 이상의 여러 수의 공통의 배수 (공배수) 중 가장 작은 수를 의미하며 수학기호로 $ LCM(a, b) $로 표현합니다.

 

---

5. 최소공배수 구하기

최소공배수는 두 수의 최대공약수를 구한 후 이를 이용하여 구할 수 있습니다.

$ LCM(a, b) = a \times b \times GCD(a, b) $

 

function getGCD(a, b) {
    if(b === 0) {
        return a;
    }
    let r = a % b;
    return getGCD(b, r)
}

function getLCM(a, b) {
    return (a * b) / getGCD(a, b);
}

 

---

마치며

유클리드 호제법을 이용한 최대공약수 도출을 기억한다면 관련된 문제는 문제없이 풀이 할 수 있습니다.
유클리드 호제법만 기억하세요