8

正の整数が 2 つの正の整数の完全な二乗和として表現できる回数を返すコードを C で書いています。

R(n) is the number of couples (x,y) such that x² + y² = n where x, y, n are all 
non negative integers.

R(n) を計算するには、まず n の素因数分解を見つける必要があります。

問題は、Cで使用できる素因数分解のアルゴリズムをたくさん試しましたが、コードをできるだけ速くする必要があることです。と同じ大きさの数の素因数分解を計算する最速のアルゴリズム2147483742.

4

2 に答える 2

12

なんて奇妙な制限でしょう。2147483742 = 2^31 + 94。

他の人が指摘したように、素数によるこの小さな試行分割は、おそらく十分に高速です。そうでない場合にのみ、Pollard の rho メソッドを試すことができます。

/* WARNING! UNTESTED CODE! */
long rho(n, c) {
    long t = 2;
    long h = 2;
    long d = 1;

    while (d == 1) {
        t = (t*t + c) % n;
        h = (h*h + c) % n;
        h = (h*h + c) % n;
        d = gcd(t-h, n); }

    if (d == n)
        return rho(n, c+1);
    return d;
}

この関数はとして呼び出され、 nrho(n,1)の (場合によっては合成された) 因数を返します。nのすべての要因を見つけたい場合は、ループに入れて繰り返し呼び出します。また、素数チェッカーも必要です。あなたの限界については、基数 2、7、および 61 を使用したラビンミラー検定が正確であり、かなり高速であることが証明されています。素数を使ったプログラミングの詳細については、私のブログを参照してください。

しかし、いずれにせよ、このような小さな制限を考えると、素数による試行除算を使用する方がよいと思います。それ以外のものは、漸近的には速くなる可能性がありますが、実際には遅くなります。

編集:この回答は最近いくつかの賛成票を受け取ったので、2,3,5ホイールでホイール因数分解を行う簡単なプログラムを追加しています。と呼ばれるこのプログラムは、 nwheel(n)の因数を昇順に出力します。

long wheel(long n) {
    long ws[] = {1,2,2,4,2,4,2,4,6,2,6};
    long f = 2; int w = 0;

    while (f * f <= n) {
        if (n % f == 0) {
            printf("%ld\n", f);
            n /= f;
        } else {
            f += ws[w];
            w = (w == 10) ? 3 : (w+1);
        }
    }
    printf("%ld\n", n);

    return 0;
}

私のブログで車輪の因数分解について説明しています。説明は長いので、ここでは繰り返しません。a に収まる整数の場合、上記longの関数を大幅に改善できる可能性は低いです。wheel

于 2012-10-06T12:19:14.917 に答える
1

候補者の数を減らす手っ取り早い方法があります。このルーチンは 2、次に 3、そして 3 で割り切れないすべての奇数を試します。

long mediumFactor(n)
{
    if ((n % 2) == 0) return 2;
    if ((n % 3) == 0) return 3;
    try = 5;
    inc = 2;
    lim = sqrt(n);
    while (try <= lim)
    {
       if ((n % try) == 0) return try;
       try += inc;
       inc = 6 - inc;  // flip from 2 -> 4 -> 2
    }
    return 1;  // n is prime
}

2 と 4 の間の inc の交互配置は、すべての偶数と 3 で割り切れる数をスキップするように慎重に調整されます。この場合: 5 (+2) 7 (+4) 11 (+2) 13 (+4) 17

少なくとも 1 つの因子が平方根以下でなければならないため、試行は sqrt(n) で停止します。(両方の係数が > sqrt(n) の場合、係数の積は n より大きくなります。)

試行回数は sqrt(m)/3 です。ここで、m はシリーズで可能な最大数です。2147483647 の制限では、2 と 3 のテストを含めて、最悪の場合 (2147483647 に近い素数の場合) の最大 15,448 除算になります。

数が合成されている場合、分割の総数は通常ははるかに少なく、それ以上になることはほとんどありません。すべての要因を取得するためにルーチンを繰り返し呼び出すことを考慮しても。

于 2014-04-15T05:14:30.923 に答える