유클리드 호제법

A와 B의 최대공약수를 G라고 하면

라고 표현할 수 있고, 이때 a와 b는 서로소이다.

A와 B의 관계는 다음과 같이 표현할 수 있다.

이 식에 첫 번째 표현을 대입하면

이렇게 표현된다. 그러므로

a - Q*n 과 b가 서로소가 아님을 가정하고, 두 수의 공약수 p로 표현하면 다음과 같다.

a와 b는 서로소이므로 p = 1이고, r과 b는 서로소이다.
그러므로 r과 B의 최대공약수는 G이다.

이걸 코드로 표현하면 다음과 같다.

    public static int gcd(int a, int b) {

        if(b == 0) return a;
        return gcd(b, a % b);
    }

처음 최대공약수를 찾은 방법은 최소값만큼 for문을 돌려 둘다 나눠지는 숫자를 최대공약수에 저장 후 반환하는 방법으로 찾았다.

    public static int gcd(int a, int b) {

        int gcd = 1;
        for(int i = 1; i <= (a < b? a: b); i++) {
            if(a % i == 0 && b % i == 0) gcd = i;
        }

        return gcd;
    }

이 경우 O(N)의 시간복잡도를 갖는데, 유클리드 호제법을 사용하면 O(logN)의 시간 복잡도를 갖는다.