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

Question

我必须找到给定数字 N 的除数总数，其中可以大到 10^14。我尝试计算最大为 10^7 的素数，然后使用素数的指数找到除数factors.However 事实证明它太慢了，因为使用筛子找到素数需要 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);
}