최대공약수와 최소공배수

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

프로그래머스

 

최대공약수와 최소공배수 문제 나오면 더 생각할 것 없이 유클리드 호제법, 유클리드 알고리즘으로 문제 풀면 되겠다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int gcd = findGCD(n, m);
        int lcm = (n * m) / gcd; // LCM을 GCD를 이용하여 계산
        
        answer[0] = gcd;
        answer[1] = lcm;
        
        return answer;
    }
    
    // 유클리드 알고리즘을 이용한 최대공약수 계산
    private int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

 

최대공약수(GCD, Greatest Common Divisor)는

https://www.freecodecamp.org/news/euclidian-gcd-algorithm-greatest-common-divisor/

이렇게 뽑을 수 있고

 

최소공배수(LCM, Least Common Multiple)는 두 수를 곱한 수를 최대공약수(GCD)로 나눠서 구한다.

그냥 이게 다다.