How to write a quick function to calculate the total divisors of a number?

Question

I have to find the total number of divisors of a given number N, where it can be like 10 14. I tried to calculate prime numbers up to 10 ^ 7, and then find divisors using indicators of a prime number of factors. However, this turns out to be too slow, since finding primes using a sieve takes 0.03 s. How can I calculate the total number of divisors faster and, if possible, without calculating prime numbers? Please rate the pseudo-code / well-explained algorithm.

Answer 1

Use the atkin sieve to find all primes less than 10 ^ 7. (of which 664 579)

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

Ideally, this should be done at compile time.

calculate the following 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; } } } 

At the end of this, you will get the full basic factorization. From this you can calculate the total number of divisors by sorting the map values: 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

I implemented the Atkin sieve on my blog but still found the optimized Eratosthenes sieve faster.

But I doubt your problem. For numbers between 10 and 14, Pollard’s factorization will beat the trial division into primes, regardless of how you generate primes. I did this on my blog .

Answer 3

You can use the Polard rho-algorithm for factorization. With all the improvements, it quickly suits numbers no less than 10 ^ 20.

Here is my implementation for factor search in Java:

 /** * Finds a factor of a number using Brent 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); } 

To divide numbers up to 10 ¹⁴ you can also just do a trial division with odd numbers up to 10 ⁷ .