import java.util.Scanner;
import java.util.LinkedList;


/* Java application that produces the prime factorizations of the numbers
** entered by the user.
**
** Authors: R. McCloskey and < STUDENTS' NAMES >
** Known Flaws: ...
*/
public class PrimeFactorize {

   private static Scanner keyboard;
   private static int depth;

   /* Repeatedly, the user is prompted to enter an integer.
   ** For each one, its prime factorization is displayed.
   ** When a number less than 2 is entered, the program terminates.
   */
   public static void main(String[] args) {
      keyboard = new Scanner(System.in);
      int n;
      do {
         n = getInt("\nEnter a positive integer (1 or less to quit): ");
         if (n > 1) {
            depth = -1;
            LinkedList<Integer> primeFactors = primeFactorizationOf(n);
            System.out.println("Prime factorization: " + primeFactors);
            int product = productOf(primeFactors);
            if (product != n) {
               System.out.println("**ERROR: product of list elements is " + product);
            }
         }
      }
      while (n > 1);

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


   // methods of interest:
   // --------------------

   /* Given a positive integer greater than 1, returns a list containing the
   ** prime factorization of that integer.
   ** Example: An input of 5390 produces a result of [2, 5, 7, 7, 11]
   */
   public static LinkedList<Integer> primeFactorizationOf(int n) {
      return primeFactorizationOfAux(n, 2);
   }

   /* Auxiliary to the method above, this recursive method produces a LinkedList
   ** containing the prime factorization of its first argument, n, under the
   ** assumption that n has no prime factors less than its second argument, k
   ** pre: 2 <= k <= n AND n % m != 0 for all m in the range [2..k)
   */
   private static LinkedList<Integer> primeFactorizationOfAux(int n, int k) {
      depth++;
      int nOrig = n;    // save the original values of the incoming parameters so
      int kOrig = k;    // that they can be printed just before the method terminates.

      printMessage(String.format("Received n:%d and k:%d\n", n, k));

      LinkedList<Integer> result;


      // MISSING CODE GOES HERE (pseudocode in writeup)


      printMessage(String.format("Having received n:%d and k:%d, " +
                                 "returning %s\n", nOrig, kOrig, result));
      depth--;
      return result;
   }



   // helper methods:
   // ---------------


   /* Returns the product of the elements in the given linked list.
   */
   private static int productOf(LinkedList<Integer> list) {
      int productSoFar = 1;
      for (int j : list) {
         productSoFar = productSoFar * j;
      }
      return productSoFar;
   }

   private static void printMessage(String s) {
      printSpaces(2*depth);
      System.out.print(s);
   }

   private static void printSpaces(int r) {
      for (int i=0; i != r; i++) { System.out.print(' '); }
   }



   /* Prints the given string and returns the integer value entered at
   ** the keyboard in response.
   */
   private static int getInt(String prompt) {
      System.out.print(prompt);
      String response = keyboard.nextLine().trim();
      return Integer.parseInt(response);
   }

}