import java.awt.*;
import java.applet.*;
import java.awt.event.*;
import java.math.BigInteger;
import java.util.Random;
import java.util.Date;

public class Factorsa extends Applet implements Runnable {
	private Thread kicker;
	Controls controls;
	Algorithm algorithm;
	private String input;
	private String output;

	BigInteger t = new BigInteger("0");
	String s = "";
	int s1 = 0;


	BigInteger zero = new BigInteger("0");
	BigInteger one = new BigInteger("1");
	BigInteger two = new BigInteger("2");

	Date d;
	long starttime;
	long finishtime;
	long duration;

	public void init() {
		controls = new Controls();
		setLayout(new BorderLayout());
		add("Center", controls);
		controls.setEnabled(true);
	}

	public void run() {
		try {
			if (algorithm == null) {
				algorithm = new Algorithm();
			}
			output = "Calculating, please wait..." + '\n';
			controls.ta.setText(output);

			algorithm.init();

			t = zero;
			s = "";
			s1 = 0;

			input = controls.tf.getText().trim();

			BigInteger n = new BigInteger("0");
			if (input.charAt(0) == 'f' || input.charAt(0) == 'F') {
				s = input.substring(1).trim();

				eval();

				n = t;

				output = output + '[' + n.toString() + ']' + '\n';
				controls.ta.setText(output);
			}
			else if (input.charAt(0) == 'r' || input.charAt(0) == 'R') {
				s = input.substring(1).trim();

				BigInteger size = new BigInteger(s);
				Random r = new Random();

				n = new BigInteger(size.intValue(), r);

				output = output + '[' + n.toString() + ']' + '\n';
				controls.ta.setText(output);
			}
			else {
				n = new BigInteger(input);
			}

			BigInteger factor = new BigInteger("0");

			d = new Date();
			starttime = d.getTime();

			do {
				factor = algorithm.factorize(n);
				if (factor.compareTo(one) > 0) {
					output = output + factor.toString() + '\n';
					controls.ta.setText(output);

					n = n.divide(factor);
				}
			} while (factor.compareTo(one) > 0 && n.compareTo(one) > 0);

			d = new Date();
			finishtime = d.getTime();

			duration = (finishtime-starttime)/1000;

			output = output + "Finished, duration = " + duration + " seconds" + '\n';
			controls.ta.setText(output);
		}
		catch (Exception e) {
		}
	}

	public synchronized void stop() {
		if (kicker != null) {
			try {
				kicker.stop();
			}
			catch (IllegalThreadStateException e) {
			}
			kicker = null;
		}
		if (algorithm != null) {
			try {
				algorithm.stop();
			}
			catch (IllegalThreadStateException e) {
			}
		}
	}

	synchronized void startCalculation() {
		if (kicker == null || !kicker.isAlive()) {
			kicker = new Thread(this);
			kicker.start();
		}
	}

	class Controls extends Panel implements ActionListener {
		TextField tf = new TextField(40);
		Button b = new Button("Calculate");
		TextArea ta = new TextArea("", 10, 60, TextArea.SCROLLBARS_VERTICAL_ONLY);

		public Controls() {
			tf.setText("Enter an integer or formula, eg F(2^61-1)^2 or R100");
			add(tf);

			b.addActionListener(this);
			add(b);

			ta.setText("Factorization by brute force, simple trial division, method");
			add(ta);
		}

		public void actionPerformed(ActionEvent ae) {
			String label = ae.getActionCommand();

			if (label.equals("Calculate")) {
				startCalculation();
			}
		}
	}

	BigInteger evalPower(BigInteger oldn, BigInteger n1, char op) {
		BigInteger n = new BigInteger("0");

		switch (op) {
		case '^':
		case '#':
			n = oldn.pow(n1.intValue());
			break;
		default:
			n = n1;
			break;
		}
		return n;
	}

	BigInteger evalProduct(BigInteger oldn, BigInteger n1, char op) {
		BigInteger n = new BigInteger("0");

		switch (op) {
		case '*':
			n = oldn.multiply(n1);
			break;
		case '/':
			n = oldn.divide(n1);
			break;
		case '%':
			n = oldn.remainder(n1);
			break;
		default:
			n = n1;
			break;
		}
		return n;
	}

	BigInteger evalSum(BigInteger oldn, BigInteger n1, char op) {
		BigInteger n = new BigInteger("0");

		switch (op) {
		case '+':
			n = oldn.add(n1);
			break;
		case '-':
			n = oldn.subtract(n1);
			break;
		default:
			n = n1;
			break;
		}
		return n;
	}

	void eval() {
		BigInteger oldn0 = new BigInteger("0");
		BigInteger oldn1 = new BigInteger("0");
		BigInteger oldn2 = new BigInteger("0");
		BigInteger n = new BigInteger("0");

		char oldop0 = 0;
		char oldop1 = 0;
		char oldop2 = 0;
		char op = 0;

		int olds1 = 0;

		while (s1 < s.length()) {
			if (s1 < s.length() && (s.charAt(s1) == '(' || s.charAt(s1) == '[' || s.charAt(s1) == '{')) {
				s1++;
				eval();
				n = t;
			}
			else if (s1 < s.length()) {
				olds1 = s1;
				while (s1 < s.length() && Character.isDigit(s.charAt(s1)))
					s1++;
				n = new BigInteger(s.substring(olds1, s1));
			}

			if (s1 < s.length()) {
				op = s.charAt(s1);
				s1++;
			}
			else
				op = 0;

			switch (op) {
				case 0:
				case ')':
				case ']':
				case '}':
					n = evalPower(oldn2, n, oldop2);
					n = evalProduct(oldn1, n, oldop1);
					n = evalSum(oldn0, n, oldop0);
					t = n;
					return;

				case '^':
				case '#':
					n = evalPower(oldn2, n, oldop2);
					oldn2 = n;
					oldop2 = op;
					break;

				case '*':
				case '/':
				case '%':
					n = evalPower(oldn2, n, oldop2);
					oldop2 = 0;
					n = evalProduct(oldn1, n, oldop1);
					oldn1 = n;
					oldop1 = op;
					break;

				case '+':
				case '-':
					n = evalPower(oldn2, n, oldop2);
					oldop2 = 0;
					n = evalProduct(oldn1, n, oldop1);
					oldop1 = 0;
					n = evalSum(oldn0, n, oldop0);
					oldn0 = n;
					oldop0 = op;
					break;
				default:
					break;
			}
		}
	}

	class Algorithm {
	protected boolean stopRequested = false;

	public void init() {
		stopRequested = false;
	}

	public void stop() {
		stopRequested = true;
	}

	public BigInteger factorize(BigInteger n) {
		BigInteger factor = new BigInteger("2");

//		int display = 1;

		while (n.compareTo(factor.multiply(factor)) >= 0) {
//			if (display == 1000) {
//				output = output + factor.toString() + '\r';
//				controls.ta.setText(output);
//				display = 1;
//			}
			if (n.remainder(factor).compareTo(zero) == 0) {
				return factor;
			}
			else {
				factor = factor.add(one);
//				display++;
				if (stopRequested)
					return one;
			}
		}

		return n;
	}
	}
}