[알고리즘] 최대공약수(GCD)와 최소공배수(LCM)

최대공약수 (Greatest Common Divisor: GCD)

최대공약수는 공약수 중 가장 큰 값을 말한다.

최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법이다.

int gcd =1;
for (int i=2;i<min(a,b);i++) {
	if (a%i==0 && b%i==0) {
		gcd=i;
	}
} //시간 복잡도 O(N)

• 유클리드 호제법

a를 b로 나눈 나머지를 r이라고 했을 때 GCD(a,b) =GCD(b,r)가 성립한다. 유클리드 호제법을 이용하면 시간복잡도를 O(logN)로 줄일 수 있다.

int GCD (int a, int b) {
	if (b ==0)
		return a;
	else
		return GCD(b,a%b);
} //재귀함수를 활용하는 방법

$GCD(24,16) = GCD(16,8) = GCD(8,0) = 8$
✔ r이 0일 때 b값이 최대공약수이다

여러 숫자의 GCD 구하는 법

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

while(1){
	int r = a%b;
   	if(r==0) return b;
		
        a = b;
        b = r;
    }//반복문을 활용하는 방법

최소공배수 (LCM)

최소공배수는 최대공약수를 응용해서 구한다

$l = a*b/GCD(a,b)$