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

   void factor(int n);

that prints out the factorization of n to the
terminal. What's the base case?  How could a
recursive 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);

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

  cout << "k = ";
  factor(k);
  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) {
  // BASE CASE
  if (n == 1)
    return;

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