私は GCD(n, i) を持っています。ここで、i=1 はループ内で n まで 1 ずつ増加しています。単純な増加よりも高速にすべての GCD を計算し、ユークリッド アルゴリズムを使用して GCD を計算するアルゴリズムはありますか?
PS n が素数である場合、1 から n-1 までの数は 1 になると想定できます。これは、素数が互いに素であるためです。素数以外の数のアイデアはありますか?
私は GCD(n, i) を持っています。ここで、i=1 はループ内で n まで 1 ずつ増加しています。単純な増加よりも高速にすべての GCD を計算し、ユークリッド アルゴリズムを使用して GCD を計算するアルゴリズムはありますか?
PS n が素数である場合、1 から n-1 までの数は 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
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;
}