/**********************************************
Using the function int firstfactor(int); that 
you guys defined for me in Class 17, write a 
recursive function 

   void factor(int n, ostream& OUT);

that prints out the factorization of n to the 
output stream OUT.  What's the base case?  How 
could a	recursive call call to factor with a 
smaller n-value help solve the problem?
**********************************************/
#include <iostream>
#include <fstream>
using namespace std;

// PROTOTYPES
int firstfactor(int);
void factor(int,ostream&);

// MAIN FUNCTION
int main()
{
  int k;
  cout << "Enter number to factor: ";
  cin >> k;

  cout << "k = ";
  factor(k,cout);
  cout << endl;

  return 0;
}


// FUNCTION DEFINITIONS

int firstfactor(int n)
{
  // Returns the smallest factor of n
  int i = 2;
  while(n % i != 0)
    i++;
  return i;
}

// Prints out all the factors of n
void factor(int n, ostream& OUT)
{
  if (n == 1) 
  {
        // No need to print the 1
        return;
  }

  // Find first factor and output that
  int a_factor = firstfactor(n);
  cout << "(" << a_factor << ")";

  // Smaller problem to print rest of factors
  int remaining = n / a_factor;
  factor(remaining, OUT);
}