[Java] 최대공약수, 최소공배수 구하기

▤ 목차

1. 최대공약수 구하기

최대공약수란 0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수이다.
여기서 유클리드 호제법을 이용하여 간편하게 최대공약수를 구할 수 있다.

유클리드 호제법의 핵심은 큰 수를 작은 수로 나누어 떨어지게 한 뒤, 수를 반복적으로 수행하여 나머지 0이 될 때까지 작동하는 방법을 의미한다. 이때 작은 수가 최대공약수다. (주의할 점은 큰 수를 작은 수로 나눠야 한다는 것)

예를 들어 1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어 떨어진다.
• 따라서, 최대공약수는 21이다.

더 자세하게 알아보려면 아래의 링크를 참고하길 바란다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

만약 유클리드 호제법을 이용하지 않는다면 아래처럼 구현하게 될 것 이다.

이는 숫자가 클수록 비효율적인 방법이 되기 때문에 이용하지 않는 편이 좋다.

int max = 0; //최대 공약수
for(int i=1; i<=num1 && i<=num2; i++) {
    	if(num1%i==0 && num2%i==0){
		max = i;
		}
	}

유클리드 호제법을 이용하면 아래처럼 두 가지 방식으로 구현할 수 있다.

// 재귀 방식
public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 반복문 방식
public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

2. 최소공배수 구하기

최소공배수는 (a✕ b) / (최대 공약수) 이므로 어렵지 않게 구할 수 있다.

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

3. 2개 이상 숫자의 최대공약수와 최소공배수 구하기

최대공약수 구하기

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

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

• arr 배열에 있는 모든 수의 “최대공약수” 구하는 것이 목표
• 반복문을 통해 배열의 나머지 값들과 최대공약수를 구하여 result 변수에 저장
• (result = arr[0]) -> (result = arr[0]와 arr[1]의 최대공약수) -> (arr[0]과 arr[1] 최대공약수와 arr[2]의 최대공약수)...
• 최종적으로 result는 배열에 있는 숫자의 최대공약수가 된다.

최소공배수 구하기

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

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

• arr 배열에 있는 모든 수의 “최소공배수” 구하는 것이 목표
• 반복문을 통해 배열의 나머지 값들과 최소공배수를 구하여 result 변수에 저장
• (result = arr[0]) -> (result = arr[0]와 arr[1]의 최소공배수) -> (arr[0]과 arr[1] 최소공배수와 arr[2]의 최소공배수)... 
• 최종적으로 result는 배열에 있는 숫자의 최소공배수가 된다.

https://adjh54.tistory.com/182#1.%20%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98(GCD)%20%EA%B5%AC%ED%98%84-1

[Java/Short] 최대공약수, 최소공배수 구하는 방법 : 두 수 또는 N개의 수

https://programmer-chocho.tistory.com/9

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

https://cobook.tistory.com/49

[Java]최대 공약수, 최소 공배수 구하기(feat.유클리드 호제법)

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.