최대공약수 / 최소공배수 알고리즘 (c++)

최대공약수 / 최소공배수 문제를 풀때 매우 유용할 것 같아서 블로그에 작성해둔다. 해당 알고리즘 문제만 나온다면 어디서든 쉽게 활용가능하니 꼭 알아두자. 

유클리드 호제법 

유클리드 호제법이란, 정수 A, B 그리고 이들의 나머지값 R이 있다고 할때,(A % B = R)
A, B의 최대공약수가 B, R의 최대공약수와 같다는 원리이다. 
이때, A와 B의 대소비교는 중요하지 않음.

 

10 % 15 = 10

15 % 10 = 5

10 % 5 = 0

-> 최대공약수: 5

이렇게 쉽게 최대공약수를 산출가능하다. 코드형식은 아래와 같다. 

int gcd(int a, int b) {
    int temp;
    while(b != 0) {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

최소공배수 구하기

그렇다면 최소공배수는? 

-> 위에서 산출했던 최대공약수를 이용하면 된다. 

두 자연수의 곱 / 최대공약수 ((A * B) / 최대공약수)

 

아래 문제들을 반복하면서 활용능력을 기르길 바란다.

프로그래머스