我必须找到给定数字 N 的除数总数,其中可以大到 10^14。我尝试计算最大为 10^7 的素数,然后使用素数的指数找到除数factors.However 事实证明它太慢了,因为使用筛子找到素数需要 0.03 秒。如何在不计算素数的情况下更快地计算除数总数?请伪代码/很好解释的算法将不胜感激。
最佳答案
使用阿特金筛法找出所有小于 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);
}
关于c++ - 如何编写一个快速函数来计算一个数的总除数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12288671/