Programmers | 코딩테스트 연습 - 최대공약수와 최소공배수(자바), 유클리드 호제법, 최소공배수 구하기

프로그래머스 Lv.1 최대공약수와 최소공배수

 

 

 

• 최대공약수 구하기 → 유클리드 호제법

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b),  a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, a=b, b=r이라 할 수 있다. 이때, b가 0이 되었을 때의(나머지가 0) a(나누는 수)가 최대공약수이다.

 

• 최소공배수 구하기

최대공약수 * 최소공배수 = a * b이다. 위의 식을 이용하여 최소공배수 = a * b / 최대공약수

 

 

JAVA

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int max = Math.max(n,m);
        int min = Math.min(n,m);
        int r = 0;
        
        //최대 공약수
        while(min > 0){
            r = max % min;
            max = min;
            min = r;
        }
        answer[0] = max;
        
        //최소 공배수
        answer[1] = n*m/max;
        
        return answer;
    }
}

유클리드 호제법을 이용하여 최대공약수를 구하고,

최대공약수 * 최소공배수 = MAX * MIN을 이용하여 최소공배수를 구하였다.

 

 

 

 

 

[참고]

https://seunghyum.github.io/algorithm/Euclidean-algorithm/

https://jisunshine.tistory.com/134