# Calculate Number of Factors of a large number.!

What algorithm can I use to calculate the number of factors of a very large number(<10^15).

I am using the following code for now and my solution is timing out.! Is there any other algorithm faster than this?

``````int calculate(int n)
{
int count=0;
for(int i=1;i<=sqrt(n);i++)
{
if(n%i==0)
{
if(n/i==i)
count++;
else
count+=2;
}
}
return count;
}``````
1 Like

You are calculating the number of divisors… is that what you ask?

• factors, to me seems to be more related with prime factors of the the number…

Hi,
Please read the editorial on Codeforces. It has a O(N ^ 1/3) solution which should pass.
http://codeforces.com/blog/entry/22317

Use MillerRabin for Primality Testing and Seive for finding primes till 10 ^ 6.

Another method is to use Pollard Rho Algorithm, find prime factorization of number.

Example 24 = (2 ^ 3) * (3 ^ 1)

Now number of divisors is (p1 + 1) * (p2 + 1) … * (pn + 1) where p1, p2 … pn are power of prime found in previous step.

In case of 24 it is (3 + 1) * (1 + 1) = 8 = number of divisors.

Implementation of Pollard Rho Algorithm.

1 Like

The most effective way which I found for the integer factorization (when values are higher than 10^12) is the Pollard’s rho algorithm… read some basics about them here: https://en.wikipedia.org/wiki/Pollard’s_rho_algorithm

regards

1 Like

For prime factors use miller rabin method…You can easily find it anywhere.

Understand and then implement.Rest if you want full code I can provide you.

@horcrux2301 If you want to calculate number of divisors of a number,you can use after sieve as explained here.

You just need to calculate prime factorization of a number and then calculate factors like if prime factorization of a number(num) is: num=a^y1+b^y2+c^y3 then

number of factors of num are (y1+1)x(y2+1)x(y3+1).

1 Like

@horcrux2301

Have a look…hope this helps.

'#include “bits/stdc++.h”

#define LL long long’

using namespace std;

#define MAXN 1000003’

bool is_prime[MAXN] = {false};

vector primes;

void sieve_eratosthenes() {

``````for(int i = 0; i < MAXN; i++)
is_prime[i] = true;

is_prime[1] = false;

for(int i = 2; i*i <= MAXN; i++){

if(is_prime[i]){

for(int j = i*i; j < MAXN; j += i){

is_prime[j] = false;

}
}
}

for(int i = 2; i < MAXN; i++)

if(is_prime[i])

primes.push_back(i);
``````

}

/* Miller Rabbin,

• Complexity: O(k * log2^3(n))

• */
inline LL multiply(LL a, LL b, const LL &m) {

a %= m, b %= m;

long double res = a;res *= b;

LL c = (LL)(res/m);

a = b, a -= cm, a %= m;

if(a < 0)

`````` a += m;
``````

return a;

}

inline LL power(LL a, LL b, const LL &m) {

``````LL ans = 1;

while(b) {

if(b & 1) {

ans = multiply(ans, a, m);

}

a = multiply(a, a, m);

b >>= 1;

}

return ans;
``````

}

// Returns true if p is prime

inline bool Miller(LL p) {

``````if(p < 2)	return false;

if(p != 2 && !(p&1))	return false;

int cnt = 0;

LL s = p-1;

while(!(s&1)) {

s /= 2;

cnt++;

}

LL accuracy = 2, m;

for(int i = 0; i < accuracy; i++) {

LL a = rand() % (p-1) + 1;

m = p;

LL x = power(a, s, m);

if(x == 1 || x == p-1)	continue;

int flag = 0;

for(int i = 1; i < cnt; i++) {

x = multiply(x, x, m);

if(x == 1)	return false;

if(x == p-1) {

flag = 1;

break;

}

}

if(flag)	continue;

return false;

}

return true;
``````

}

LL count_divisors(LL n)

{

``````LL ans = 1;

int sze=primes.size();

for(int i=0;i<sze;i++) {

LL p=primes[i];

if(p*p*p > n)	break;

LL count = 1;

while(n % p == 0) {

n /= p;

count++;

}

ans = ans*count;

}

LL sq = sqrt(double(n));

if(Miller(n)) {
ans = ans*2;

}

else if(sq*sq == n && Miller(sq)) {

ans *= 3;

}

else if(n != 1) {

ans *= 4;

}

return ans;
``````

}

int main() {

``````sieve_eratosthenes();

LL n;

cin >> n;

cout << count_divisors(n) << endl;

return 0;
``````

}

In this problem I need to calculate the number of factors.! @ymondelo20

Answer could be Pollard’s rho algorithm… in this case.

Yes. Can you please provide me the implementation in C++?

https://ideone.com/5929qz .
I ran the code above and it gave me 4 as output for 11 as input. Something is wrong with the code.!