[JAVA] 프로그래머스 Lv1. 최대공약수와 최소공배수

<문제>

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

<제한 사항>

• 두 수는 1이상 1000000이하의 자연수입니다.

<풀이>

 

class Solution {

    public int[] solution(int n, int m) {

        int a = Math.max(n,m);

        int b = Math.min(n,m);

        while(b!=0){           

            int tmp = a%b;

            a = b;

            b = tmp;

        } // 최소공배수 a

 

        int c = a*(n/a)*(m/a);

        int[] answer = {a,c};

        return answer;

    }

}

 

*유클리드 호제법*

  :  a와 b의 최대공약수는 a를 b로 나눈 나머지n과 b의 최대공약수와 같다.

     b의 값이 0이 될때 까지 나누고 그때의 a값이 최대 공약수이다.

 

*최소공배수 구하기*

 : a와b를 각각 최대공약수로 나눈 후 최대공약수 와 곱한 값이다.

=> 최대공약수 c * (a/c) * (b/c)