[c++] 유클리드 호제법으로 최대공약수(GCD)와 최소공배수(LCM) 구하기

'유클리드 호제법'이란?

유클리드 호제법(혹은 유클리드 알고리즘)은 빠르게 최대공약수(GCD)를 구하는 알고리즘입니다.

참고로 GCD는 Greatest Common Divisor의 약어!

LCM은 Least Common MultiPle의 약어!

 

'유클리드 호제법'의 원리

두 자연수 a, b가 주어졌을 때,

a를 b로 나눈 나머지가 temp라고 하면,

temp가 0일 때 b가 최대공약수(GCD)입니다.

만약 temp가 0이 아니면

a에 b값을 넣고, b에 temp값을 넣은 다음

위 과정을 반복합니다.

 

'유클리드 호제법'의 구현 방법

반복문을 이용해 구현하거나

재귀함수를 이용해서 구현할 수 있습니다.

 

먼저 반복문을 이용해 구현하는 법을 소개하겠습니다.

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

b가 0이 될 때까지

반복문을 돌게됩니다.

 

직접 뇌버깅을 해봅시다.

a = 6, b = 4라고 가정합니다.

 

b는 0이 아니니까

temp는 2가 됩니다.

그 후 a와 b는 각각 4, 2가 됩니다.

 

또, b는 0이 아니니까

temp는 0이 됩니다.

그 후 a와 b는 각각 2와 0이 됩니다.

 

이 때, b는 0이 되므로

리턴되는 a가 최대공약수(GCD)라고 할 수 있습니다.

 

마찬가지로, 재귀함수는 다음과 같이 구현할 수 있습니다.

int gcd(int a, int b) {
    if (b == 0) {
    	return a;
    } else {
    	gcd(b, a%b);
    }
}

재귀함수로 구현했을 시에는

swap을 위한 과정이 필요없다는 장점이 있지만

재귀함수의 특성상 메모리를 많이 잡아먹기도 합니다.

 

이렇게 최대공약수(GCD) 구하는 법을 알아봤습니다.

다음으로는 최소공약수(LCM)를 알아보겠습니다.

최소공약수(LCM)을 구하기 위해서는 아래와 같은 성질을 이용합니다.

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

이를 이용해서 구현하면 아래와 같습니다.

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

이만 글을 마치겠습니다.

감사합니다.

 

알고리즘은 알면 알수록 어렵습니다.

개발자 꿈꾸는 주니어들 도망가.