[Java]-최대공약수&최소공배수

최대공약수

최대공약수는 유클리드 호제법을 이용한다.

a = b*q + r

유클리드 호제법의 원리는 a와 b의 최대공약수는 b와 r의 최대공약수랑 같다는 원리이다.

최소공배수

최소공배수는 a*b를 a,b의 최대공약수로 나눠주면 된다.

코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        answer[0] = gcd(n,m);
        answer[1] = lcm(n,m);
        return answer;
    }

    public int gcd(int a, int b){//최대 공약수
        while(b != 0){
            int temp = a%b;
            a = b;
            b = temp;
        }
        return a;
    }
    public int lcm(int a, int b){//최소 공배수
        return (a*b)/gcd(a,b);
    }
}