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

public class Pollard
{ 
    public static void main(String[] args)
    {
        System.out.println("Enter a positive integer to be factored");
	ConsoleReader console = new ConsoleReader(System.in);
        String inputString = console.readLine();
        BigInteger zed = new BigInteger("0");
        BigInteger one = new BigInteger("1");
        BigInteger num = new BigInteger(inputString,10);
        //System.out.println(num);
        BigInteger gcdab = new BigInteger("1");
        BigInteger first = new BigInteger("5");
        BigInteger second = new BigInteger("1");
        second = first.multiply(first);
        int count = 1;
        int success = 0;
        boolean  primeornot = false;
         primeornot = num.isProbablePrime(16);
        BigInteger difference = new BigInteger("0");
    if (primeornot == false)
    {
        while((count < 6000) & success==0)
          {   
              difference = first.subtract(second);  
	      gcdab = difference.gcd(num);
              System.out.println(gcdab);
              if (zed.equals(gcdab)) 
		  break;
              if (gcdab.compareTo(one)==1)
		  success = 1;
              else
		  {first = first.multiply(first);
		  first = first.add(one);
                  first = first.mod(num);
                  second = second.multiply(second);
                  second = second.add(one);
                  second = second.multiply(second);
                  second = second.add(one);
                  second = second.mod(num);
                  }
              count++;
              if (count == 1000)
		{  first = one;
		second = first.add(one);
                }
          }    
	if (success == 1)
	    System.out.println("a factor of "+num+ " is "+gcdab); 
    }
    else 
    	System.out.println(num + " is prime ");    
    }
}