[JAVA] 최대 공약수(GCD), 최소 공배수(LCM) 구하기

최대 공약수 구하는 방법

1. 숫자가 2개인 경우 

 

1) 두 수를 공약수로 계속 나눈다. 

2) 공약수로 나눈 몫이 서로소가 되면 stop 

3) 왼쪽 공약수를 모두 곱한다. 

 

∴ 60 과 48의 최대 공약수 : 2 ✕ 2 ✕ 3 = 12

 

2. 숫자가 3개 이상인 경우

- 코드에서 배열이 매개변수로 주어지는 경우

 

1. 모든 수를 동시에 반드시 나눌수 있는 수로 나눈다. 

2. 더이상 동시에 나눌 수 없으면 stop 

3. 왼쪽 공약수를 모두 곱한다. 

 

∴ 60, 48, 40 의 최대공약수 : 2 ✕ 2 = 4

---

최소 공배수 구하는 방법

1. 숫자가 2개인 경우

1) 두 수의 공약수로 나눈 몫이 서로소가 될 때까지 나눈다. 

2) 왼쪽 공약수들과 아래 서로소까지 모두 곱한다. 

 

∴ 60 과 48의 최소 공배수 : 2 ✕ 2 ✕ 3 ✕ 5 ✕ 4= 240

 

2. 숫자가 3개 이상인 경우 

- 코드에서 배열이 매개변수로 주어지는 경우

1) 서로소가 아닌 수가 2개라도 있으면 그 수들의 공약수로 나눈다.
   나누어 떨어지지 않는 수는 그대로 밑에 내려온다. 

2) 모든 몫이 서로소이면 stop 

3) 왼쪽 공약수와 아래 서소로를 모두 곱한다.

 

∴ 60, 48, 40 의 최소 공배수 : 2 ✕ 2  ✕ 2 ✕ 3 ✕ 5 ✕ 1 ✕ 2 ✕ 1= 240

---

유클리드 호제법 

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

원리는 다음과 같다. 

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

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

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

 

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

최소 공배수 : (a ✕  b) / (최대 공약수)

 

ex) 60, 48 의 최대공약수 :
     60 % 48 = 12
     48 % 12 = 0 // 최대 공약수 : 12

// 최소 공배수 : (60 ✕ 48) / 12 = 240

 

만약 수가 여러개라면 최소 공배수를 어떻게 구하면 될까?

숫자 A,B,C 가 있을 경우

1) A,B의 최소 공배수를 구한다. 
2) 1에서 구한 A,B의 최소 공배수와 C의 최소공배수를 구한다. 

---

[JAVA code]

유클리드 호제법을 이용한 코드이다. 

1. 숫자가 2개인 경우

package com.algorithm.level2;

import java.util.Arrays;
import java.util.Stack;

public class Test12 {
    public static void main(String[] args) {
        int num1 = 60;
        int num2 = 48;

        int gcd = getGCD(num1, num2);
        System.out.println("the greatest common denominator : " + gcd);
        System.out.println("the lowest common multiple : " + (num1 * num2) / gcd);
        
    }

    public static int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1%num2);
    }
}

 

2. 숫가 여러개일 때  (매개변수 배열)

package com.algorithm.level2;

public class Test12 {
    public static void main(String[] args) {
        int[] arr = {2, 6, 8, 14};

        System.out.println("the lowest common multiple : " + getLCM(arr));
    }

    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;
    }

    public static int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1 % num2);
    }
}