// Arup Guha
// 11/1/07
// Phollard-Rho Factoring Algorithm

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

public class PollardRho {

  	public static void main(String[] args) {

    	Scanner stdin = new Scanner(System.in);
    
    	// Initial values of a and b in the algorithm.
    	BigInteger a = new BigInteger("2");
    	BigInteger b = new BigInteger("2");

		// Get the number to factor.
    	System.out.println("Enter the number to factor.");
    	String val = stdin.next();
    	BigInteger n = new BigInteger (val);
    	BigInteger d = null;

		// Keep on going, we'll break out of the loop based on a couple
		// conditions.
    	while (true) {

      		// Operate on a once, and b twice.
      		a = (a.multiply(a).add(BigInteger.ONE)).mod(n);
      		b = (b.multiply(b).add(BigInteger.ONE)).mod(n);
      		b = (b.multiply(b).add(BigInteger.ONE)).mod(n);

      		// We want the gcd of the difference of a and b and d.
      		d = n.gcd(a.subtract(b));

			// We got lucky and found a factor!
      		if (!d.equals(BigInteger.ONE) && !d.equals(n))
        		break;

			// This means we won't ever find one in this manner.
      		if (d.equals(n))
        		break;
     	}

		// Output the appropriate message.
     	if (d.equals(n))
       		System.out.println("Test failed, couldn't factor.");
     	else
       		System.out.println(n+" = "+(d)+" * "+n.divide(d));

  }
}