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