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?
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.
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++?
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))
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.!