I tried to solve this problem :

FACT1_SPOJ

I know since the value of N is upto 10^20, I had to use a generalized algorithm such as pollard rho.. and I did.

Still my verdict is given TLE. Can someone please help me to show the optimization that can be done?

Here is my code

import java.util.*;
import java.math.*;
import java.security.*;

public class Main {
	final static BigInteger ZERO = new BigInteger("0");
	final static BigInteger ONE = new BigInteger("1");
	final static BigInteger TWO = new BigInteger("2");
	public static BigInteger prm[]=new BigInteger[10000];
	public static int l;
	
	public static SecureRandom random = new SecureRandom();
	
	public static BigInteger pollard_rho(BigInteger n)
	{
		BigInteger d;
		BigInteger k = new BigInteger(n.bitLength(), random);
		BigInteger x = new BigInteger(n.bitLength(),random);
		BigInteger y = x;
		while(true)
		{
			x = ((x.multiply(x)).add(k).mod(n));
			y = ((y.multiply(y)).add(k).mod(n));
			y = ((y.multiply(y)).add(k).mod(n));
			d = (x.subtract(y).gcd(n));
			if(d.compareTo(ONE) != 0) break;
		}
		return d;
	}
	public static void factorize(BigInteger n)
	{
		if(n.compareTo(ONE) == 0) return;
		if(n.isProbablePrime(30))
		{
			prm[l++]=n;
			return;
		}
		
		BigInteger d = pollard_rho(n);
		
		factorize(d);
		factorize(n.divide(d));
	}
	
	public static void main(String[] args)
	{
		Scanner scanf = new Scanner(System.in);
		int i;
		BigInteger n;
		
		while(scanf.hasNext()) //this means while(input != EOF)
		{
			n = scanf.nextBigInteger();
			
			if(n.compareTo(ZERO) == 0)break;
			
			l = 0;
			
			while(true)
			{
				if((n.mod(TWO)).compareTo(ZERO) != 0)break;
				n = n.divide(TWO);
				prm[l++] = TWO;
			}
			factorize(n);
			
			if(l == 0) continue;
			
			Arrays.sort(prm, 0, l);
			
			int cnt = 1;
			boolean flag = false;
			
			for(i = 1; i < l; i++)
			{
				if(prm[i].compareTo(prm[i-1]) == 0)
				{
					cnt++; continue;
				}
				if(flag) System.out.print(" ");
				flag = true;
				System.out.print(prm[i-1] + "^" + cnt);
				cnt = 1;
			}
			if(flag)System.out.print(" ");
			System.out.print(prm[i-1] + "^" + cnt);
			System.out.println("");
		}
		scanf.close();
	}
}