[알고리즘 지식] 최대공약수(GCD) 최소공배수(LCM) 구하기

알고리즘을 풀다가 최대공약수를 구해야하는 상황이 있었다.

그림을 그려서 최대공약수를 구할 수 있지만 코드로 어떻게 풀어내는지는 다른 문제였다.

그렇다면 코드로 어떻게 풀 수 있을까? 

 

유클리드 호제법

2개의 수의 최대공약수를 구하는 알고리즘이다.

원리는 다음과 같다.

자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 한다면 a,b의 최대공약수와 b,r의 최대공약수는 같다. 

이 성질에 따라 a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지 r'을 구한다.  

나머지가 0이 될때 나눈 수가 a,b의 최대공약수가 된다. 

 

유클리드 호제법으로 최대 공약수를 구한 다음, 최소 공배수는 다음 식에 의해 구할 수 있다.

숫자가 두개일 때 최소 공배수 : (a ✕  b) / (최대 공약수)

 

숫자가 두개인 경우 최대 공약수 구하는 식

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

숫자가 여러개인 경우 최소 공배수 구하는 식

   public static int getLCM(int[] arr) {
        if (arr.length == 1) {
            return arr[0];
        }

        int gcd = getGCD(arr[0], arr[1]);
        int lcm = (arr[0] * arr[1]) / gcd;

        for (int i = 2; i < arr.length; i++) {
            gcd = getGCD(lcm, arr[i]);
            lcm = (lcm * arr[i]) / gcd;
        }

        System.out.println("the greatest common demoniator : " + gcd);

        return lcm;
    }

(출처https://programmer-chocho.tistory.com/9 감사합니당💜)