/* bigfactor implements prime factoring for arbitrary-precision
   numbers using Java 1.1+ BigInteger class 
                                      M. Gallant  1/98         */

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

public class bigfactor {
  static final BigInteger zero = new BigInteger("0") ;
  static final BigInteger one = new BigInteger("1") ;
  static final BigInteger two = new BigInteger("2") ;
  static final BigInteger three = new BigInteger("3") ;

    public static void main(String argv[]) {
        for (int i = 0; i < argv.length; i++) {
            try {
                BigInteger number = new BigInteger(argv[i]);
                  if (number.compareTo(zero) <= 0)
                    continue;
                System.out.print(number + " = ");
                Vector factors = getFactors(number);
                for (int j = 0; j < factors.size(); j++) {
                    if (j != 0)
                        System.out.print(" * ");
                    System.out.print((BigInteger) factors.elementAt(j));
                }
                System.out.println();
                System.out.println(verifyFactors(number, factors)) ;
            } catch (NumberFormatException e) {
              }
        }
    }


    static Vector getFactors(BigInteger number) { // number should be positive
        Vector factors = new Vector();

        while (number.mod(two).compareTo(zero) == 0) {
              // System.out.println("New factor: " + two) ;
            number=number.divide(two);
            factors.addElement(two);
        }

        BigInteger limit = bigRoot(number).add(one);
          // System.out.println("Initial search limit: " + limit) ;
factor:
        for (BigInteger i = three; i.compareTo(limit) <= 0; i=i.add(two)) {
            while (number.mod(i).compareTo(zero) == 0) {
                  // System.out.println("New factor: " + i) ;
                number=number.divide(i) ;
                factors.addElement(i);
                if (number.compareTo(one) == 0)
                    break factor;
                limit = bigRoot(number).add(one);
            }
        }

        if (number.compareTo(one) != 0 || factors.size() == 0)
            factors.addElement(number);

        return factors;
    }


   static BigInteger bigRoot(BigInteger number) {
    BigInteger result = zero ;
    BigInteger oldRoot ;
    BigInteger newRoot ;
    BigInteger zero=new BigInteger("0") ;
    BigInteger two =new BigInteger("2") ;

    BigInteger num = number ; 
    newRoot = num.shiftRight(num.bitLength()/2) ;
    do {
     oldRoot = newRoot ;
     newRoot = oldRoot.multiply(oldRoot).add(num).divide(oldRoot).divide(two) ;
     //System.out.println("" + oldRoot + "  " +newRoot) ; 
     //System.out.println("" + newRoot.subtract(oldRoot).abs().compareTo(two)) ;
    } while(newRoot.subtract(oldRoot).abs().compareTo(two)>0) ;

     // System.out.println("Root of "+ num + ": " + newRoot) ;
    return newRoot;
   }


   static String verifyFactors(BigInteger number, Vector factors) {
          String status = "" ;
          BigInteger check = one;  //initialize check product of factors.
           for(int k = 0; k < factors.size() ; k++) 
             check = check.multiply((BigInteger) factors.elementAt(k)) ;
           if(check.compareTo(number) ==0)
             status = "Factor Verification OK ------------------------------" ;
            else
             status = "!!!!! Problem with verifying product of factors !!!!!";
         return status ;
   }


}