최소공배수와 최대공약수

📄 언어 : C++

---

🔶 풀이 방식

유클리드 호제법이라는것을 이용해서 쉽게 최소공배수와 최대공약수를 찾아낸다.

- 최대공약수(Greatest Common Divisor): 주어진 수들의 공통된 약수 중 가장 큰 자연수 
- 최소공배수(Least Common Multiple): 주어진 수들의 공통된 배수 중 가장 작은 자연수

✔ 유클리드 호제법

나머지연산 %를 반복하여 최대공약수를 찾아내는 방법!
큰 수를 작은수로 나머지연산을 하고, 그 수와 나눈 수를 다시 나머지연산을 반복한다.

두 수는 모두 최대공약수의 배수이므로, 나머지연산을 한 이후의 수도 마찬가지로 최대공약수의 배수인 상태이다. 따라서 이를 반복하다가 나누어 떨어지게 되는 경우, 그 수가 바로 최대공약수가 되는 것이다.

나머지연산을 한 수가 왜 최대공약수의 배수인지를 수식으로 보기쉽게 나타내보자.
자연수 a , b 와 두 수의 최대공약수를 L이라고 할때

$A = a1 * L$,
$B = b1 * L$,
$A - B = (a1 - b1) *L$
— 위 식을 보면 A-B를 해도 최대공약수 L을 항상 포함하고 있다.
% 연산 역시 - 연산을 반복한 것과 비슷한 연산이므로 마찬가지로 적용할 수 있다!
따라서 % 연산을 한 나머지도 역시 최대공약수의 배수임을 알 수 있다.

---

✔ 두 수의 최대공약수(GCD) 구하기

    //반복문을 이용하기
    int gcd(int a, int b)
    {
        int t;
        while(b!=0)
        {
            t = a % b;
            a= b;
            b= t;
        }
        return a;
    }

    //재귀를 이용하기
    int gcd(int a, int b)
    {
        return b == 0? a :gcd(b, a % b);
    }

👍 핵심 코드

1. 두 수를 % 연산을 하여 나머지를 구한다.
2. 나머지로 구해진 값과, 나머지연산을 한 수를 다시 % 연산한다
3. 나머지가 0이 될때까지 반복한다

---

✔ 두 수의 최소공배수(LCM) 구하기

두 수 a b의 최대공약수와 최소공배수사이에는 다음과 같은 관계가 있다고 한다.

$lcm(a*b) * gcd(a,b) = a*b$

이를 최소공배수에 대하여 정리해보면

$lcm(a,b) = a * b / gcd(a,b)$

와 같은 식을 얻어낼 수 있다. 따라서 최소공배수를 구하는 코드는 다음과 같다.

    int lcm(int a, int b)
    {
        return a * b / gcd(a,b);
    }

👍 핵심 코드

1. 두 수를 곱한 후 최대공약수로 나누어준다.
2. 최소공배수는 공통된 소인수의 최대 지수 거듭제곱들의 곱이므로,
3. 두 수의 곱에서 공통 인수인 최대공배수로 나눠버리면 공통부분이 전부 사라지며 서로다른 부분만 남게 된다.
4. 즉 이 값이 최소공배수가 된다.

---

(포스트번호: algorithm-01)

TOP