/*******************************************
** This program reads an integer from the
** user and prints out its factorization
** into irreducibles.  You need to figure 
** out how to implement the function 
** firstFactor, which takes an integer n, 
** where n > 1, and returns the smallest 
** factor of n, i.e. the smallest
** integer greater than 1 that divides n
** evenly.  Specifically, you need to add 
** the definition of the function firstFactor.
*******************************************/
#include <iostream>
using namespace std;
 
/*******************************************
** firstFactor FUNCTION PROTOTYPE
*******************************************/
int firstFactor(int);
 
/*******************************************
** MAIN FUNCTION
*******************************************/
int main()
{
  // Get integer n, n > 1, from user
  int n;
  cout << "Enter an integer larger than 1: ";
  cin >> n;
 
  // Print out factorization
  cout << "The factorization of " << n << " is ";
  while(n > 1)
  {
    // get & print next irreducible factor
    int f = firstFactor(n);
    cout << '(' << f << ')';
    n = n / f;
  }
  cout << endl;
 
  return 0;
}

 
/*******************************************
** firstFactor FUNCTION DEFINITION goes below these lines
*******************************************/
int firstFactor(int n)
{
	//declare
	int factor;

	//initialize
	factor = 2;

	// Solution 1
	while(n % factor != 0)
	{
		factor++;
	}
	
	/* Solution 2
	while(factor <= n)
	{
		if (n % factor == 0)
		{
			//return factor;
			break;
		}

		factor++;
	}
	*/

	return factor;
}