/**********************************************
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;
}

void factor(int n, ostream& OUT)
{
  // BASE CASE
  if (n == 1)
    return;

  // RECURSIVE CASE
  int f = firstfactor(n);
  OUT << '(' << f << ')';
  factor(n/f,OUT);
}