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: Pollard's rho algorithm - Wikipedia
regards
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).
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;
}
Answer could be Pollard’s rho algorithm… in this case.
Yes. Can you please provide me the implementation in C++?
5929qz - Online C++0x Compiler & Debugging Tool - Ideone.com .
I ran the code above and it gave me 4 as output for 11 as input. Something is wrong with the code.!