자바 - 최대공약수와 최소공배수 구하기

프로그래머스 문제를 풀다가 최대공약수와 최소공배수 푸는 법을 간단하게 정리해 보았다.

(참고 문제: 최대공약수와 최소공배수)

프로그래머스

 

문제와 예시

 

먼저 최대공약수는 for문을 돌리면서 주어진 두 숫자의 나머지를 0으로 만드는 최대 숫자를 구하는 방식을 사용하였다.

for (int i=1; i<=Math.min(n,m);i++) {
    if (n%i==0 && m%i==0) {
        answer[0] = i;
    }
}

 

최소공배수는 두 수를 곱한 후 최대공약수로 나누는 방식을 사용하였다.

answer[1] = n*m/answer[0];

 

최대공약수를 사용하는 방법으로는 유클리드 호제 방식을 많이 사용한다고 하는데 해당 방식을 참고해 봐도 될 것 같다.

 

 

작성한 답변

public class Main {
    public static void main(String[] args) throws IOException {
        int n = 3;
        int m = 12;
        int[] answer = new int[2];

        // 최대공약수
        for (int i=1; i<=Math.min(n,m);i++) {
            if (n%i==0 && m%i==0) {
                answer[0] = i;
            }
        }
        // 최소공배수
        answer[1] = n*m/answer[0];
        System.out.println("answer = " + Arrays.toString(answer));
    }
}