최대 공약수와 최소 공배수

- 최대 공약수

 

최대공약수란 두수 A와 B의 공통된 약수 중에서 가장 큰 정수이다

 

최대 공약수를 구하는 가장 쉬운 방법은 2부터 A와 B중 작은 수 까지의 모든 정수로 두 수를 나누어 보는 것이다.

코드로 구현해보면 아래와 같다

 

int g = 1;
for(int i = 2; i <= min(a,b); i++) {
    if(a % i == 0 && b % i ==0){
        g = i;
    }
}

 

이렇게 하면 g는 공약수를 만날 때 마다 바뀌겠지만

어차피 2부터 A와 B중 작은 수 까지 해당 연산을 반복하니 최종적으로 G엔 가장 큰 공약수가 저장되게 되어 있다

 

( 물론 최대공약수가 1로 그냥 나올 수도 있다. 이런 두수는 서로소라고 한다 )

 

이 연산의 시간복잡도는 N을 max(a,b)로 했을때 O(N)과 같다

 

나쁜 방법은 아니지만 유클리드 호제법이란 걸 활용하면 더 빠르게 최대 공약수를 구할 수 있다.

 

A를 B로 나눈 나머지를 r이라고 했을 때

A와 B의 최대공약수는 B와 r의 최대공약수와 같다.

 

따라서 B와 r의 나머지 연산을 해서 r이 0이 될 때의 B가 A와 B의 최대공약수이다.

 

공식으로 표현하자면 GCD (a,b) = GCD(b, a%b) 이고 

GCD(24,16) = GCD(16,8) = GCD (8,0) = 8 이다.

 

코드로는 두가지 방식으로 표현할 수 있는데

먼저 재귀함수를 활용하면 

 

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

 

와 같이 표현할 수 있고 반복문을 활용해서도

 

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

 

와 같이 표현할 수 있다

 

이렇게 하면 시간 복잡도가 O(logN)으로 매우 짧아진다.

그렇기에 최대 공약수를 구해야 할 일이 있으면 아래와 같은 방법은 활용하자

 

- 최소 공배수

 

최소공배수란 두 수의 공통된 배수 중에서 가장 작은 정수다.

 

최소 공배수는 최대 공약수를 응용해서 구할 수 있는데

두 수 A 와 B 를 곱한 값이 두 수의 최대 공약수와 최소 공배수를 곱한 값과 같기 때문이다.

 

따라서 두 수의 최소공배수 = (A X B) / 최대공약수 의 공식을 활용해 구할 수 있다