Link to question :https://www.spoj.com/problems/DIVSUM2/

My approach : -> Find all prime factors of the number below 1 million . Store the frequency of prime factors in a vector while repeatedly dividing the number by the factor , then use the formula to calculate the sum of factors .

->Now if there is a number left ,then that will be either prime or product of two primes. I try to check primality using Miller–Rabin. If number is not prime , then using rho-pollard , I try to generate one of the prime factors , divide to get another and then proceed accordingly.

However, I am getting TLE. I would like to know where I am going wrong . Is it the implementation or the approach ? Thank you.

#include<bits/stdc++.h>

using namespace std;

#define MOD 10000000007

using ll = unsigned long long ;

const ll million=1000000;

vector<ll>v(50000);

ll pow_expo(ll a,ll b)
{

    ll res=1;
    while(b>0)
    {
        if(b&1)
            res=res*a;
        a=a*a;
        b>>=1;
    }
return res;
}


ll pow_exp(ll a,ll b,ll n)
{
    a%=n;
    ll result=1;
    while(b>0)
    {
        if(b&1)
            result=result*a%n;
        a=a*a%n;
        b>>=1;
    }
return result;
}

bool miller_rabin_test(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=pow_exp(a,d,n);
    if(x==1||x==n-1)
        return true;
    while(d!=n-1)
    {
        x=(x*x)%n;
        d*=2;
        if(x==1)
            return false;
        if(x==(n-1))
            return true;
    }
return false;
}

bool is_prime(ll n,ll k)
{
    if(n<=1||n==4)
    return false;
    if(n==2||n==3)
        return true;
    ll d=(n-1);
    while(d%2==0)
    {
        d/=2;
    }
    for(int i=1;i<=k;i++)
    {
        if(!miller_rabin_test(d,n))
            return false;
    }

return true;
}

ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    a%=b;
        return gcd(b,a);
}

ll f(ll x)
{
    return ((x*x)+1);
}
ll rho_pollard(ll n)
{
     if(n%2==0)
        return 2;

    ll x=rand(),y=rand(),d=1;

    while(d==1)
    {
        x=(f(x))%n;

        y=(f(f(y)))%n;

        d=gcd(abs(x-y),n);
    }

    return d;
}

ll factorize(ll n)
{
    ll temp=n;
    for(int i=2;i*i<=n;i++)
    {
        if(i>million)
            break;
        while(n%i==0)
        {
            v[i]++;
            n/=i;
        }
    }
    ll sum=1;
        for(ll i=2;i<v.size();i++)
        {
            if(v[i]>0)
                sum*=(pow_expo(i,v[i]+1)-1)/(i-1);
        }

  if(n>1&&is_prime(n,3))
  {
      sum*=(n+1);
       return (sum-temp) ;
  }
  else if(n>1)
  {
            int f1=rho_pollard(n);
            int f2=n/f1;
            sum*=(f1+f2+2);
             return (sum-temp) ;
  }
return (sum-temp) ;

}

int main()
{
    ll q;
    scanf("%I64d",&q);
    while(q--)
    {
        ll n;
        scanf("%I64d",&n);
        fill(v.begin(),v.end(),0);
        printf("%I64d\n",factorize(n));
    }


}