# SPOJ FACT1 Prime factorization up to 10^20

I have implemented the brent’s algorithm.
But still i am getting TLE.

``````#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

ll mul(ll a, ll b, ll mod)
{
ll res=0;
while(b)
{
if(b&1)
res=(res%mod+a%mod)%mod;
a=(a%mod + a%mod)%mod;
b>>=1;
}
return res;
}

ll f(ll x, ll c, ll n)
{
return (mul(x,x,n)+c)%n;
}

ll binpower(ll a, ll b, ll p)
{
ll res=1;
while(b)
{
if(b&1)
res = mul(res,a,p);
a = mul(a,a,p);
b>>=1;
}
return res;
}

bool fermant(ll n, ll k)
{
if(n<=1||n==4)
return 0;
if(n<=3)
return 1;
if(n%2==0)
return 0;
vector<ll> primes={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
for(auto i:primes)
if(i==n)
return 1;

for(ll i=1;i<=k;++i)
{
ll a=2+rand()%(n-4);
if(__gcd(a,n)!=1)
return 0;
if(binpower(a,n-1,n)!=1)
return 0;
}
return 1;
}

ll brent(ll n)
{
ll g=1;
ll x,y,xs,q=1;
srand(time(NULL));
x=(rand()%(n-2))+2;
ll c=(rand()%(n-1))+1;
int l=1;
int m=128;//Num of times multiplied
while(g==1)
{
y=x;
for(int i=1;i<l;++i)
x=f(x,c,n);
int k=0;
while(k<l&&g==1)
{
xs=x;
int i=0;
while(i<m&&i<(l-k))
{
x=f(x,c,n);
q=mul(q,abs(y-x),n);
++i;
}
g=__gcd(q,n);
k+=m;
}
l*=2;
}
if(g==n)
{
do
{
xs=f(xs,c,n);
g=__gcd(abs(xs-y),n);
}while(g==1);
}
return g;
}

int main() {
map<ll,ll> fac;
ll p;
while(1)
{
ll n;
cin>>n;
if(n==0)
break;
fac.clear();
while(n!=1)
{
p=brent(n);
while(!fermant(p,20))
p=brent(n);
n/=p;
fac[p]++;
}
for(auto i=fac.begin();i!=fac.end();++i)
cout<<i->first<<"^"<<i->second<<" ";
cout<<endl;
}
return 0;
}``````