我怎么能写一个快速的函数来计算的总人数约数？ [英] How can I write a fast function to calculate total divisors of a number?

问题描述

我要找到一个给定数量N分频器的总数在哪里可以大到10 ^ 14。我尝试了计算高达10 ^ 7的素数，然后找到使用的主要的指数除数factors.However是谈到了将作为查找使用筛素数太慢需要0.03秒。我如何计算速度更快的除数，如果可能的总数不计算质数？请伪code /很好地解释算法将大大AP preciated。

I have to find the the total number of divisors of a given number N where can be as large as 10^14 .I tried out calculating the primes upto 10^7 and then finding the the divisors using the exponents of the prime factors.However it is turning out to be too slow as finding the primes using the sieve takes 0.03 s. How can I calculate the total number of divisors faster and if possible without calculating the primes? Please pseudo code /well explained algorithm will be greatly appreciated.

推荐答案

使用阿特金的筛找到所有素数小于10 ^ 7。 （有这些664579）

Use the sieve of atkin to find all of primes less than 10^7. (there are 664,579 of these)

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

理想，这应该在编译时完成。

ideally this should be done at compile time.

下一个计算的主要因子：

next compute the prime factorization:

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;
     }
  }
}

在本月底，你将有完整的主要因子。从这里就可以通过遍历地图的价值计算除数总数： <一href="http://math.stackexchange.com/questions/66054/number-of-combinations-of-a-multiset-of-objects">http://math.stackexchange.com/questions/66054/number-of-combinations-of-a-multiset-of-objects

At the end of this, you will have the complete prime factorization. From this you can compute the total number of divisors by iterating over the values of the map: http://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);
}

这篇关于我怎么能写一个快速的函数来计算的总人数约数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！