/* bigfactorapplet factors arbitrarily large integer using basic
   resursive modular division           
                                      M. Gallant    01/99       */

import java.awt.*;
import java.applet.*;
import java.io.*;
import java.util.*;
import java.math.BigInteger;

public class bigfactorapplet extends Applet
    {

      PrimeFactors primethread ;
      public TextArea textArea = new TextArea (15, 60);
      public TextField tf1 = new TextField("156377653664",30 ) ;
      Button factornumber = new Button("Factor") ;
      Button clearbutton = new Button("Clear Text") ;
      Button stopbutton = new Button("Stop") ;

    public void init ()
        {
       factornumber.setBackground(Color.red) ;
       clearbutton.setBackground(Color.white) ;

            add (clearbutton) ;
            add (stopbutton) ;
            add (tf1) ;
            add (factornumber) ;
            add (textArea);
          primethread = new PrimeFactors(this, new BigInteger(tf1.getText())) ;         
         }       


   public void stop() {
      if(primethread.isAlive())
        primethread.stop() ;
       textArea.appendText("Factorization stopped!\n") ;
      }

   public boolean action(Event evt, Object arg) {     //intercept AWT action.
    if (evt.target == clearbutton) {
     textArea.setText("") ;
     return true ;
     }
    else
    if (evt.target == stopbutton) {
      if(primethread.isAlive()) {
         primethread.stop() ;
         textArea.appendText("Factorization stopped!\n") ;
        }
     return true ;
     }
    else
      if (evt.target == factornumber) {
 
         if(!primethread.isAlive()) {
           try {
              primethread = new PrimeFactors(this, new BigInteger(tf1.getText())) ; 
              primethread.start() ;
               }
                catch (NumberFormatException e) {
                 textArea.append(" !!!Bad number format !!!\n\n") ;
                }
          }

         return true;
       }              // end if
     else return false;
   }                 // end action handler


 }  // end bigfactorapplet class  


class PrimeFactors extends Thread {
  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") ;
    bigfactorapplet caller ;
    TextArea textArea ;
    BigInteger number ;
   
    PrimeFactors(Applet appl, BigInteger number){    
       this.caller = (bigfactorapplet)appl;
       this.textArea = caller.textArea ;
       this.number = number ;
      }


     public void run() {
            try {
                textArea.append(number + " = ");
                Vector factors = getFactors(number);
                for (int j = 0; j < factors.size(); j++) {
                    if (j != 0)
                        textArea.append(" * ");
                    textArea.append("" + (BigInteger) factors.elementAt(j));
                }
                  textArea.append("\n");
                  textArea.append(verifyFactors(number, factors)+"\n\n") ;
            } catch (NumberFormatException e) {
              textArea.append(" !!!Bad number format !!!\n\n") ;}
      }    // end run()


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

        while (number.mod(two).compareTo(zero) == 0) {
            number=number.divide(two);
            factors.addElement(two);
        }

        BigInteger limit = bigRoot(number).add(one);
factor:
        for (BigInteger i = three; i.compareTo(limit) <= 0; i=i.add(two)) {
            while (number.mod(i).compareTo(zero) == 0) {
                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;
    }


   private 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) ;
    } while(newRoot.subtract(oldRoot).abs().compareTo(two)>0) ;

    return newRoot;
   }


   private 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 ;
   }

}