[수학] 유클리드 호제법; 최대공약수를 구하는 빠른 방법

소개

임의의 2개 수에 대한 최대공약수를 구하는 과정에 대하여, 각 수를 임의의 수로 나눠보는 과정 없이 빠르게 최대공약수를 구해내는 방법

 

개념

두 양의 정수 a, b에 대하여, a = bq + r (0 ≤ r < b)일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

만약 r이 0이라면, a와 b의 최대공약수는 b이다.

public static int gcd( int a, int b ) {
    int r = a % b;
    while( r != 0 ) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

시간복잡도: O(logn)

 

원리

[수학알고리즘] 유클리드 호제법

[수학알고리즘] 유클리드 호제법

임의의 수 A와 B에 대하여 (A ≥ B),

만약 두 수의 최대공약수가 G일 때, 각 수는 다음과 같이 표현할 수 있다:

A = Ga, B = Gb (a, b: 서로소)

 

이때, A를 B로 나눈 몫을 Q, 나머지를 R이라 할 때,

A = BQ + R

Ga = GbQ + R

Ga - GbQ = R

G (a - bQ) = R

이때, a - bQ는 임의의 정수이므로 R은 G를 약수로 가진다

 

따라서 A를 만들어내기 위해 존재하는 B와 R의 최대공약수를 구하는 과정은

A와 B의 최대공약수를 구하는 과정과 같다

 

결론적으로, B와 R을 위의 방법대로 반복하여 R이 0이될 때,

해당시점에서 B의 위치에 들어가는 값은 최초 연산된 A와 B의 최대공약수이다.

(A = BQ형식이 된다는 뜻인데, A가 B의 정수배라는 뜻이 되기 때문)

 

개념: 활용

• 다항식의 최대공약수 산출
• n개 숫자들의 최대공약수

 

관련 문제

최대공약수와 최소공배수

숨바꼭질 6 (17087)

GCD 합 (9613)