[Java/문법] 최대공약수(GCD), 최소공배수(LCM), 여러 수의 최소공배수 구하기

✏️ 최대공약수(GCD)

• 유클리드 호제법을 사용해 구할 수 있습니다.
• b가 0이 될 때까지 a를 b로 나눈 나머지를 계산합니다.

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

 

---

 

✏️ 최소공배수(LCM)

• 최대공약수를 이용해 구할 수 있습니다.
• 두 수의 곱 / 최대공약수로 나누면 최소공배수를 구할 수 있습니다.

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

 

---

✏️ 여러 수의 최소공배수

• 배열의 첫 번째 요소부터 시작해서 순차적으로 각 요소와의 최소공배수를 구할 수 있습니다.

public static int lcmOfArray(int[] arr) {
	int result = arr[0];
    for (int i = 1; i < arr.length; i++) {
    	result = lcm(result, arr[i]);
    }
    return result;
}