[알고리즘] 유클리드 호제법 - 최대공약수 / 최소공배수 구하기

▶️ 유클리드 호제법

: 유클리드 알고리즘, 최대 공약수 구하는 알고리즘

소인수분해 후 공통된 소수를 찾으면 된다.

a, b를 나누어 떨어지게 하는 수 중 가장 큰 수 찾기

> 유클리드 알고리즘은 쉽게 말하면 MOD(나머지 구하기)라고 할 수 있다.

 

▶️예시

24와 18의 최대공약수(GCD)

i) A = 24 / B = 18 인 경우

    GCD(24, 18) -> GCD(18, 6) -> GCD(6, 0) = 6

a) 24 % 18 = 6     b) 18 % 6 = 6 (최대공약수)     c) 6 % 6 = 0

 

278과 192의 최대공약수(GCD)

ii) A = 278 / B = 192 인 경우

    GCD(278, 192) -> GCD(192, 78) -> GCD(78, 36) -> GCD(36, 6) -> GCD(6, 0) = 6

a) 278 % 192 = 78     b) 192 % 78 = 36     c) 78 % 36 = 6     d) 36 % 6 = 6 (최대공약수)     e) 6 % 6 = 0

 

 

▶️JAVA 재귀함수 사용

public static int GCD(int a, int b) {
    if (b == 0) return a;
    return GCD(b, a%b);
}

 

▶️최소공배수(LCM)

GCD를 이용하여 최소공배수(LCM) 도 구할 수 있다.

public static int LCM(int a, int b) {
    return a * b / GCD(a, b);
}