[프로그래머스/자바] 최대공약수와 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

항상 최대공약수와 최소공배수를 찾는 문제는 연습문제 풀 때마다 찾아보고 다음 문제를 풀 때에는 기억을 못하는거 같아서 이 기회에 정리해놓으려고 한다.

 

최대공약수는 두 수 사이에 가장 큰 공통 약수이고, 최소공배수는 두 수의 배수 중 가장 작은 공통 배수이다.

 

최대공약수는 1부터 두 수 중 작은 수까지 중에서 두 수를 모두 0으로 나누어 떨어지는 수 중 가장 큰 수이다. 그렇기에 i를 1부터 두 수 중 작은 수(min)까지 1씩 증가시키면서 조건을 만족하는 수로 바꿔주면 된다.

최소공배수는 두 수의 곱을 위에서 구해준 최대공약수로 나눠주면 된다.

 

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int min = Math.min(n,m);
        for(int i=1;i<=min;i++){
            if(n%i==0 && m%i==0){
                answer[0] = i;
            }
        }
        answer[1] = (n*m)/answer[0];
        return answer;
    }
}