import CS99.*;

/**
 * PrimeFactorization - Lab 6
 * Author: Michael Clarkson
 * NetID: mrc26
 * Date: 7/11/00
 */
class PrimeFactorization {

	public static void main(String[] args) {
	
		System.out.println("Prime Factorization");
		System.out.println("-------------------");
		
		boolean done = false;	// is the user done executing the program?
		
		do {
			int num = getNumToFactor();
			primeFactor(num);
			done = getDoneWithProgram();
		} while (!done);

		System.out.println("Bye.");
	
	}

	/**
	 * Yield a number to factor, input from System.in, validated
	 * to be >= 2.
	 */
	static int getNumToFactor() {
		int num;	// number input from System.in

		System.out.println();
		
		boolean valid = false;	// was the input valid?
		do {
			System.out.print("Enter the number to factor: ");
			num = Console.readInt();
			if (num < 2) {
				System.out.println("Number must be greater than 1");
			} else {
				valid = true;
			}
		} while (!valid);
		
		return num;
	}

	/** 
	 * Yield whether the user is done executing the program
	 */
	static boolean getDoneWithProgram() {
		String response;	// String input from System.in
		boolean done = false;		// whether the user answered s/he was done or not
		
		boolean valid = false;		// was the input valid?
		do {
			System.out.print("Another number (yes or no)? ");
			response = Console.readString();

			char firstChar = response.toUpperCase().charAt(0);	// the first character in response

			if (firstChar == 'Y') {
				valid = true;
			} else if (firstChar == 'N') {
				valid = true;
				done = true;
			} else {
				System.out.println("You must answer yes or no.");
			}

		} while (!valid);
		
		return done;
	}

	/**
	 * Print the prime factorization of num to System.out
	 * as a sum of exponentiations.  Print "<num> is prime"
	 * if num is prime.  num must be >= 2.
	 */
	static void primeFactor(int num) {
		boolean first = true;		// is this the first output the method has produced?
		int originalNum = num;		// original value of num passed to procedure
		
		int testFactor = 2;			// current test factor of num
		while (num != 1) {
			if (isDivisibleBy(num, testFactor)) {
				int p = highestPower(num, testFactor);	// greatest power of testFactor that divides num

				if (originalNum != testFactor) {
					if (!first) {
						System.out.print(" + ");
					} else {
						System.out.print(num + " = ");
						first = false;
					}

					System.out.print(testFactor);
					if (p > 1) {
						System.out.print("^" + p);
					}
				} else {
					System.out.print(num + " is prime");
				}

				num = num / pow(testFactor, p);
			}
			testFactor++;
		}
		
		System.out.println("\n");
	}
	
	/**
	 * Yield whether num is evenly divisible by factor.
	 */
	static boolean isDivisibleBy(int num, int factor) {
		return num % factor == 0;
	}

	/**
	 * Yield the highest power p such that factor^p evenly
	 * divides num.
	 */
	static int highestPower(int num, int factor) {
		int p = 1;
		
		while (isDivisibleBy(num, pow(factor, p))) {
			p++;
		}
		
		return p-1;
	}

	/**
	 * Yield base raised to the exponent as an integer
	 */	
	static int pow(int base, int exponent) {
		return (int) Math.pow(base, exponent);
	}
	
}