[프로그래머스] 최대공약수와 최소공배수 (lv.1)

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

코딩테스트 연습 - 최대공약수와 최소공배수

 

[문제 풀이]

 

1. 유클리드 호제법을 이용하여 최대공약수를 구할 수 있다.

  1-1. GCD(a, b) = GCD(b, r)

  1-2. b = 0일 때 a의 값이 최대공약수이다.

2. 최소공배수 * 최대공약수는 = A * B 이므로 최소공배수는 A * B / GCD로 구할 수 있다.

 

[소스 코드]

 

import java.util.Arrays;

public class GCDAndLCM {
    public static void main(String[] args) {
        int n = 2;
        int m = 5;

        System.out.println(Arrays.toString(solution(n, m)));
    }

    private static int[] solution(int n, int m) {
        int gcd = gcd(n, m);
        int lcm = n * m / gcd;

        return new int[]{gcd, lcm};
    }

    private static int gcd(int n, int m) {
        if (m == 0) {
            return n;
        }

        return gcd(m, n % m);
    }
}