[Java] 프로그래머스 - 최대공약수와 최소공배수

 

 

1. 최대공약수

// 숫자가 2개일 경우
public int getGcd(int a, int b){
	if(b == 0) {
    	return a;
    }    
    return getGcd(b, a%b);
}

// 숫자가 여러개일 경우

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

 

 

2. 최소공배수

최소공배수는 최소공배수를 구할 두 수를 곱한 값을 최대공약수로 나눈 값과 같다.

public class Main {
    // 두 숫자의 최대공약수를 구하는 함수
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    // 두 숫자의 최소공배수를 구하는 함수
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    // 여러 숫자의 최소공배수를 구하는 함수
    public static int lcmOfMultipleNumbers(int[] numbers) {
        int result = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            result = lcm(result, numbers[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] numbers = {12, 18, 24, 36};
        int result = lcmOfMultipleNumbers(numbers);
        System.out.println("여러 숫자의 최소공배수: " + result); // 출력: 72
    }
}