최대공약수와 최소공배수

문제

풀이

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        int a = Math.max(n,m);
        int b = Math.min(n,m);
        while(b!=0){
            int r = a % b;
            a = b;
            b = r;
        }
        
        answer[0]= a;
        answer[1]= n*m / a;
        
        return answer;
    }
}

유클리드 호제법

1.최대공약수 -> 유클리드 호제법
임의의 두 자연수 a, b(a > b)가 주어지고
a를 b로 나눈 나머지를 r(r = a % b)로 이라고 하자.
a=b가되고 b=r이 되는데 , 이때 b가 0이될떄의 a가 최대 공약수이다.

2.최소공배수 -> a*b/최대공약수