최대공약수와 최소공배수

문제 : 최대공약수와 최소공배수

풀이

int[] answer = new int[2];

• [최대공약수, 최소공배수] 배열이므로 길이가 2인 배열을 선언

answer[0] = gcd(n, m); // 최대 공약수
answer[1] = m * n / answer[0]; // 최소 공배수

• 배열은 0부터 시작이므로 answer[0]에는 최대공약수, answer[1]에는 최소공배수 지정

• 유클리드 호제법에 의해 최대 공약수는 gcd(n,m)

• 최소공배수 : 최대 공약수를 구한 뒤 두 수의 곱 / 최대공약수

public static int gcd(int n, int m) {
        if (m == 0) return n; // gcd(a,b) = gcd(b,r) => r = a % b
        else return gcd(m, n % m);
    }

• 재귀문을 사용하여 최대 공약수 구하기

• 만약 m이 0이라면 n을 반환하고 종료

• 그게 아니라면 m과 n%m의 최대 공약수를 반환

• gcd(a,b) = gcd(b,r) => r --> n % m(n을 m으로 나눈 나머지)

• r = a%b ==> a%b에서 a<b일경우 a%b = a

전체 코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        // [최대공약수,최소공배수]
        // 유클리드 호제법 : 최대 공약수를 구한 뒤 두 수의 곱 / 최대공약수 = 최소공배수
        answer[0] = gcd(n, m); // 최대 공약수
        answer[1] = m * n / answer[0]; // 최소 공배수
        return answer;
    }
    public static int gcd(int n, int m) {
        if (m == 0) return n; // gcd(a,b) = gcd(b,r) => r = a % b
        else return gcd(m, n % m);
    }
}