[TIL] - 유클리드 호제 - 최소공배수와 최대공약수

유클리드 호제 (Euclidean algorithm)

 - 2개의 자연수 혹은 정식의 최대공약수(gcd)를 구하는 알고리즘의 하나이다.

 - 2개의 자연수 a,b에 대하여 r을 a%b (a>b) 라고 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

 - 결론적으로 b%r 인 r'를 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수가 된다.

 - 최소공배수는 두 자연수 (a*b)/gcd(a,b) 이다.

 

 

관련 문제

코딩테스트 연습 - N개의 최소공배수 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[python]

from math import gcd
def solution(arr):
    answer = arr[0]
    for num in arr:
        answer = (answer * num) // gcd(answer,num)
    return answer

 

pytyon은 math 라이브러리에서 최대공약수를 구하는 함수를 제공하기 때문에 유클리드 호제법을 사용하지 않고도

n개의 최소공배수를 구해낼 수 있다. 

 

[java]

class Solution {
    public int solution(int[] num) {
        int answer = num[0];
        for(int i=0;i<num.length;i++){
            answer = answer*num[i] /gcd(answer,num[i]);  
        }
        return answer;
    }

    public int gcd(int a, int b) {
        return (a % b == 0) ? b : gcd(b, a % b);
    }

    public static void main(String[] args) {
        Solution c = new Solution();
        int[] text = { 1, 3, 5, 34 };
        System.out.println(c.solution(text));
    }
}

자바에서는 gcd() 메소드를 만들어 유클리드 호제법을 이용하여 최대공약수를 구할 수 있도록 해주었다.

본문에서는 재귀를 이용하여 구현하였다.