c++ - 如何编写一个快速函数来计算一个数字的总除数？

Question

我必须找到给定数字 N 的除数总数，其中可以大到 10^14。我尝试计算素数到 10^7，然后使用素数因子的指数找到除数。但是结果太慢了，因为使用筛子找到素数需要 0.03 秒。如何在不计算素数的情况下更快地计算除数的总数？请伪代码/很好解释的算法将不胜感激。

Answer 1

使用阿特金筛法找出所有小于 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);
}

Answer 2

我在博客中实现了阿特金筛，但仍然发现优化的埃拉托色尼筛更快。

但我怀疑这是你的问题。对于大至 10^14 的数字，无论您如何生成素数，Pollard rho 分解都将击败素数的试除法。我在我的博客上也是这样做的。

Answer 3

您可以使用Pollard 的 rho 算法进行因式分解。有了所有的改进，至少 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}的奇数进行试除法。