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

}

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

}