4

与えられた数 N の約数の総数を見つける必要があります。ここで、10^14 まで大きくなる可能性があります。10^7 までの素数を計算してから、素因数の指数を使用して約数を見つけようとしましたが、ふるいを使用して素数を見つけるには 0.03 秒かかるため、遅すぎることが判明しています。可能であれば素数を計算せずに、除数の総数をより速く計算するにはどうすればよいですか? 疑似コード/よく説明されたアルゴリズムをお願いします。

4

3 に答える 3

4

アトキンのふるいを使用して、10^7未満のすべての素数を見つけます。（これらは664,579個あります）

http://en.wikipedia.org/wiki/Sieve_of_Atkin

理想的には、これはコンパイル時に実行する必要があります。

次に素因数分解を計算します。

int x; // the number you want to factor
Map<int to int> primeFactor; // this is a map that will map each prime that appears in the prime factorization to the number of times it appears.

while(x > 1) {
  for each prime p <= x {
     if x % p == 0 {
       x = x / p; 
       primeFactor(p) = primeFactor(p) +1;
     }
  }
}

これが終わると、完全な素因数分解ができます。これから、マップの値を反復処理することにより、除数の総数を計算できます： https ://math.stackexchange.com/questions/66054/number-of-combinations-of-a-multiset-of-objects

int result = 1;
for each value v in primeFactors {
  result*= (v+1);
}
于 2012-09-05T20:12:16.037 に答える
1

因数分解には、ポラードのロー アルゴリズムを使用できます。すべての改善により、少なくとも 10^20 までの数値を高速に処理できます。

Javaで因子を見つけるための私の実装は次のとおりです。

/**
 * Finds a factor of a number using Brent's algorithm.
 *
 * @param n  The number.
 *
 * @return  A factor of n.
 */
public static BigInteger findFactor(BigInteger n)
{
    final BigInteger result;
    if (n.isProbablePrime(80))
    {
        result = n;
    }
    else
    {
        BigInteger gcd = n;
        BigInteger c = ONE;
        while (gcd.equals(n))
        {
            int limitPower = 0;

            long k = 0;
            BigInteger y = ONE;
            boolean done = false;
            while (!done)
            {
                limitPower++;
                final long limit = Numbers.pow(2, limitPower);
                final int productLimit = (int) Numbers.pow(2, limitPower / 2);

                final BigInteger x = y;
                while (!done && k < limit)
                {
                    final BigInteger savedY = y;
                    int j = 0;
                    final int jLimit = (int) Math.min(productLimit, limit - k);
                    BigInteger p = ONE;
                    while (j < jLimit)
                    {
                        y = next(n, c, y);
                        p = p.multiply(x.subtract(y)).mod(n);
                        j++;
                    }
                    gcd = Numbers.gcd(p, n);

                    if (gcd.equals(ONE))
                    {
                        // Move along, nothing to be seen here
                        k += jLimit;
                    }
                    else
                    {
                        // Restart and find the factor
                        y = savedY;
                        while (!done)
                        {
                            k++;
                            y = next(n, c, y);
                            gcd = Numbers.gcd(x.subtract(y), n);
                            done = !gcd.equals(ONE);
                        }
                    }
                }
            }
            c = c.add(ONE);
        }
        result = gcd;
    }
    return result;
}


private static BigInteger next(BigInteger m, BigInteger c, BigInteger x)
{
    return square(x).subtract(c).mod(m);
}

10 14までの数を素因数分解するには、10 7までの奇数で試行除算を行うこともできます。

于 2012-09-23T06:51:28.827 に答える
1

ブログでアトキンのふるいを実装しましたが、最適化されたエラトステネスのふるいの方が高速であることがわかりました。

しかし、それがあなたの問題だとは思いません。10^14 の大きさの数の場合、素数を生成する方法に関係なく、ポラードのロー因数分解は素数による試算除算よりも優れています。私のブログでもそうしました。

于 2012-09-05T21:03:12.087 に答える