algorithm - 高速反復 GCD

Question

私は GCD(n, i) を持っています。ここで、i=1 はループ内で n まで 1 ずつ増加しています。単純な増加よりも高速にすべての GCD を計算し、ユークリッド アルゴリズムを使用して GCD を計算するアルゴリズムはありますか?

PS n が素数である場合、1 から n-1 までの数は 1 になると想定できます。これは、素数が互いに素であるためです。素数以外の数のアイデアはありますか?

Answer 1

まとめ

gcd の可能な答えは、n の因数で構成されます。

これらを次のように効率的に計算できます。

アルゴリズム

最初に、n を素因数の積に因数分解します。つまり、n=p1^n1*p2^n2*..*pk^nk です。

次に、n のすべての要素をループし、n の要素ごとに、その位置にある GCD 配列の内容を要素に設定できます。

要素が適切な順序 (ソートなど) で実行されていることを確認すると、複数回書き込まれた配列エントリが最高値 (gcd) で書き込まれることがわかります。

コード

以下は、数値 1400=2^3*5^2*7 に対してこれを行う Python コードです。

prime_factors=[2,5,7]
prime_counts=[3,2,1]
N=1
for prime,count in zip(prime_factors,prime_counts):
    N *= prime**count

GCD = [0]*(N+1)
GCD[0] = N
def go(i,n):
    """Try all counts for prime[i]"""
    if i==len(prime_factors):
        for x in xrange(n,N+1,n):
            GCD[x]=n
        return
    n2=n
    for c in xrange(prime_counts[i]+1):
        go(i+1,n2)
        n2*=prime_factors[i]
go(0,1)    
print N,GCD

Answer 2

C++ 実装、O(n * log log n) で動作します (整数のサイズが O(1) であると仮定):

#include <cstdio>
#include <cstring>
using namespace std;

void find_gcd(int n, int *gcd) {
  // divisor[x] - any prime divisor of x
  //              or 0 if x == 1 or x is prime
  int *divisor = new int[n + 1];
  memset(divisor, 0, (n + 1) * sizeof(int));

  // This is almost copypaste of sieve of Eratosthenes, but instead of
  // just marking number as 'non-prime' we remeber its divisor.
  // O(n * log log n)
  for (int x = 2; x * x <= n; ++x) {
    if (divisor[x] == 0) {
      for (int y = x * x; y <= n; y += x) {
        divisor[y] = x;
      }
    }
  }

  for (int x = 1; x <= n; ++x) {
    if (n % x == 0) gcd[x] = x;
    else if (divisor[x] == 0) gcd[x] = 1; // x is prime, and does not divide n (previous line)
    else {
      int a = x / divisor[x], p = divisor[x]; // x == a * p
      // gcd(a * p, n) = gcd(a, n) * gcd(p, n / gcd(a, n))
      // gcd(p, n / gcd(a, n)) == 1 or p
      gcd[x] = gcd[a];
      if ((n / gcd[a]) % p == 0) gcd[x] *= p;
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  int *gcd = new int[n + 1];
  find_gcd(n, gcd);
  for (int x = 1; x <= n; ++x) {
    printf("%d:\t%d\n", x, gcd[x]);
  }
  return 0;
}