최대공약수와 최소공배수 (프로그래머스) - Java

해결 방법 

최대공약수(gcd)는 유클리드 알고리즘을 사용하여 풀었다.

유클리드 알고리즘 (gcd, 최대공약수)

최소공배수(lcm)는 두 수의 배수 중에서 가장 작은 값 이므로, 두 수를 곱한 부분에 최대 공약수를 나누어 준 값이 최소공배수가 된다. 

 

코드 구현은 다음과 같다.

class Solution { 
    private int gcd(int a, int b) {
        int c;
        
        while(b != 0) {
            c = a % b;
            a = b;
            b = c;
        }
        return a;
    }
    
    private int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
    
    public int[] solution(int n, int m) {
        int[] answer = {gcd(n, m), lcm(n, m)};
        return answer;
    }
}