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

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.


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

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

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

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).

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

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

}

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.!