1. 개요

수학에서 0이 아닌 두 정수 의 GCD 는 각 정수를 균등하게 나누는 가장 큰 양의 정수입니다.

이 사용방법(예제)에서는 두 정수의 최대 공약수 (GCD)를 찾는 세 가지 접근 방식을 살펴 봅니다. 또한 Java에서 구현되는 방법을 살펴 보겠습니다.

2. 무차별 대입

첫 번째 접근 방식에서는 1부터 주어진 가장 작은 숫자까지 반복하고 주어진 정수가 인덱스로 나눌 수 있는지 확인합니다. 주어진 숫자를 나누는 가장 큰 인덱스는 주어진 숫자 의 GCD입니다.

int gcdByBruteForce(int n1, int n2) {
    int gcd = 1;
    for (int i = 1; i <= n1 && i <= n2; i++) {
        if (n1 % i == 0 && n2 % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

보시다시피, 위 구현의 복잡성은 O (min (n1, n2))입니다. 왜냐하면 GCD를 찾기 위해 n 번 (작은 숫자에 해당) 루프를 반복해야하기 때문 입니다.

3. 유클리드의 알고리즘

둘째, 유클리드의 알고리즘을 사용하여 GCD를 찾을 수 있습니다. Euclid의 알고리즘은 효율적일뿐만 아니라 이해하기 쉽고 Java에서 재귀를 사용하여 구현하기도 쉽습니다.

유클리드의 방법은 두 가지 중요한 정리에 따라 달라집니다.

  • 첫째, 큰 숫자에서 더 작은 숫자를 빼면 GCD는 변하지 않습니다. 따라서 숫자를 계속 빼면 결국 GCD가됩니다.
  • 둘째, 작은 숫자가 더 큰 숫자를 정확하게 나눌 때 작은 숫자는 주어진 두 숫자의 GCD입니다.

구현시 기본적으로 한 번에 많은 뺄셈이 수행되므로 뺄셈 대신 모듈로를 사용할 것입니다.

int gcdByEuclidsAlgorithm(int n1, int n2) {
    if (n2 == 0) {
        return n1;
    }
    return gcdByEuclidsAlgorithm(n2, n1 % n2);
}

또한, 주 우리는 사용하는 방법 N2 에서 N1 위치를의와 알고리즘의 재귀 단계에서 N2의 위치에서 나머지 부분을 사용합니다 .

또한 Euclid 알고리즘 의 복잡성 은 O (Log min (n1, n2)) 로 이전에 보았던 Brute Force 방법에 비해 더 좋습니다.

4. Stein의 알고리즘 또는 이진 GCD 알고리즘

마지막으로, Binary GCD 알고리즘이라고도 하는 Stein의 알고리즘을 사용 하여 두 개의 음이 아닌 정수의 GCD를 찾을 수 있습니다. 이 알고리즘은 산술 이동, 비교 및 ​​빼기와 같은 간단한 산술 연산을 사용합니다.

Stein의 알고리즘은 두 개의 음이 아닌 정수의 GCD를 찾기 위해 GCD와 관련된 다음 기본 ID를 반복적으로 적용합니다.

  1. gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
  2. 때 N1 과 N2는 모두 짝수 정수하고있다 (N1, N2) = 2 * GCD GCD (N1 / 2, N2 / 2) (2)가 공약수이기 때문에,
  3. 경우 N1은 짝수이고, N2는 다음의 홀수의 정수이다 GCD (N1, N2) = GCD (N1 / 2, N2) (2)가 성립 공약수 역도 아니므
  4. 경우 N1 과 N2는 모두 홀수 정수가되고, N1> N2 = 다음 GCD (N1, N2) = GCD ((N1-N2) / 2, N2) 반대 역도

n1 이 n2 또는 n1 = 0 이 될 때까지 2-4 단계를 반복합니다 . GCD는 (2 n ) * n2 입니다. 여기서 n 은 2 단계를 수행하는 동안 n1 과 n2 에서 2가 공통적으로 발견되는 횟수입니다 .

int gcdBySteinsAlgorithm(int n1, int n2) {
    if (n1 == 0) {
        return n2;
    }

    if (n2 == 0) {
        return n1;
    }

    int n;
    for (n = 0; ((n1 | n2) & 1) == 0; n++) {
        n1 >>= 1;
        n2 >>= 1;
    }

    while ((n1 & 1) == 0) {
        n1 >>= 1;
    }

    do {
        while ((n2 & 1) == 0) {
            n2 >>= 1;
        }

        if (n1 > n2) {
            int temp = n1;
            n1 = n2;
            n2 = temp;
        }
        n2 = (n2 - n1);
    } while (n2 != 0);
    return n1 << n;
}

2로 나누거나 곱하기 위해 산술 시프트 연산을 사용하는 것을 볼 수 있습니다. 또한 주어진 숫자를 줄이기 위해 빼기를 사용합니다.

n1> n2 가 O ((log 2 n1) 2 ) 인 경우 Stein 알고리즘의 복잡성 . 때, N1 <N2, 그것이 O ((로그 2 N2) 2 ).

5. 결론

이 예제에서는 두 숫자의 GCD를 계산하는 다양한 방법을 살펴 보았습니다. 또한이를 Java로 구현하고 복잡성을 빠르게 살펴 보았습니다.

항상 그렇듯이 여기에있는 예제의 전체 소스 코드는 항상 GitHub에 있습니다 .