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.
Asked
Active
Viewed 4,749 times
4
-
2@ColinD: No ,absolutely no .I was just trying to solve some other problem on SPOJ where I needed to calculate the total number of divisors.. – thedarkknight Sep 05 '12 at 19:50
-
Getting the number of divisors can't be done without prime factorisation as far as I know. The good news is that there are more efficient algorithms for prime factorisation than a simple sieve. – biziclop Sep 05 '12 at 19:50
-
@biziclop:in that case how can the prime factorization be found quicker? – thedarkknight Sep 05 '12 at 19:51
-
http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number – Colin D Sep 05 '12 at 19:52
-
1I don't think calculating primes up to 10^7 under 0.03s is to be considered slow... – Sep 05 '12 at 19:53
-
@ColinD:I had gone through that question before posting,however none of the answers gave a detailed algorithm to solve the problem.Even the links provided weren't too good. – thedarkknight Sep 05 '12 at 19:54
-
Check out this link: http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number – alvonellos Sep 05 '12 at 19:55
-
Why do you need to compute the list of primes more than once? Surely computers have memory for that purpose. – Sep 05 '12 at 19:56
-
2if 0.03 seconds is your to slow? please give an estimate of your target time and your system specs. – Colin D Sep 05 '12 at 19:57
-
@H2CO3 I assume the primes are pre-calculated and 0.03s is the time for performing the trial divisions. Although 10^14 isn't that big that using an advanced algorithm would make much of a difference. – biziclop Sep 05 '12 at 20:01
-
One way you can improve performance is to do the factor searching in parallel assuming that you have more than 1 CPUs. – biziclop Sep 05 '12 at 20:06
-
Then go assembly, do overclock, assemble oily-coolers 0.03s->0.02s not enough? Make your code parallell+buy nvidia tesla x5. 0.03->0.0001 – huseyin tugrul buyukisik Sep 05 '12 at 20:06
-
@biziclop 0.03s for sieving the primes to 10^7 seems about right. Problem is that the testing machines SPOJ uses are old and slow, so it'll take much longer there. – Daniel Fischer Sep 05 '12 at 20:07
-
no 0.03 is the time to sieve out the primes . – thedarkknight Sep 05 '12 at 20:12
-
http://www.alpertron.com.ar/ECM.HTM factors 14 digit numbers instantaneously. It uses something called Elliptic Curve Method. – Will Ness Sep 06 '12 at 16:10
3 Answers
4
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;
}
}
}
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: 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);
}
-
1`p <= sqrt(x)` is enough, although you'd want to calculate it only once and store it in a separate variable. – biziclop Sep 05 '12 at 20:23
-
@Colin D Except for the fact that I have used the sieve of Eratosthenes instead of Atkin's ,I have done exactly the same steps.How much performance will this change make? – thedarkknight Sep 05 '12 at 20:27
-
-
@ColinD: I am aware of that fact,however I was asking u to quantify the difference it will make in terms of the running time – thedarkknight Sep 05 '12 at 20:31
-
-
1The sieve you use shouldn't make any difference though, as you pre-calculate all the primes and store them in an array. – biziclop Sep 05 '12 at 20:45
-
@ColinD:Sir could you give me some pointers about implementing Atkins sieve.the code on wiki looks quite abstract – thedarkknight Sep 05 '12 at 20:54
-
it looks like there is an implementation here: http://thomasinterestingblog.wordpress.com/2011/11/30/generating-primes-with-the-sieve-of-atkin-in-c/ I would start there and then start caching duplicate caclulations (in the nested for loops, they calculate x*x a couple times when x hasnt changed) – Colin D Sep 05 '12 at 20:59
-
@thedarkknight Python pseudocode for sieve of Atkin can be seen here http://stackoverflow.com/a/110404/849891 . Your problem though isn't finding primes, but finding prime factorization, for which trial division takes too long, correct? Seems like Pollard's rho is your ticket. – Will Ness Sep 10 '12 at 06:38
1
I implemented the Sieve of Atkin at my blog, but still found an optimized Sieve of Eratosthenes to be faster.
But I doubt that's your problem. For numbers as large as 10^14, Pollard rho factorization will beat trial division by primes, no matter how you generate the primes. I did that at my blog, too.
user448810
- 17,381
- 4
- 34
- 59
-
@Sir I did read about the Pollard Rho factorization but was wondering whether it would be an overkill to implement it.Sir,I am not able to understand the implementation on your blog – thedarkknight Sep 05 '12 at 21:07
-
-
@thedarkknight: I put a Python version of a simple pollard rho factoring program at http://ideone.com/u9r6W; your c++ implementation should be similar. This shows why pollard rho is so fast; even with a limit of 100 steps it was able to compute the factorization, whereas trial division would require 664578 divisions for this composite number. That's an extreme example, to be sure, but if you are trial dividing by primes greater than 1000, it's probably better to switch to pollard rho. – user448810 Sep 05 '12 at 23:46
-
@thedarkknight: By the way, trial division is O(n ^ 1/2). Pollard rho is O(n ^ 1/4), which is very much better than trial division. – user448810 Sep 06 '12 at 02:05
1
You can use Pollard's rho-algorithm for factorization. With all the improvements it is quick for numbers up to at least 10^20.
Here is my implementation for finding a factor in 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);
}
To factorize numbers up to 1014 you could also just do trial division with odd numbers up to 107.
starblue
- 55,348
- 14
- 97
- 151