//  Executes Fermat's Factorization 
//  Algo 2.10 p 159 in 
//  Discrete Mathematical Sturctures: Theory and Applications
//  by D.S. Malik and M.K. Sen

#include <iostream> //for terminal i/o
#include <fstream>  //for file i/o
#include <stdlib.h>
#include <stdio.h>
#include <string>

using namespace std;


//*********************************** MAIN *****************************************

int main()
{

	double n; 					// Input composite number	
	int x,y;				// Intermediate numbers
	int a,b;				// Factors
	char resp;				// Indicates if trace is desired (Y,N) 
	

//*********************************** Read Input **************************************

	cout << "Fermat's Factorization Algorithm" << endl;
	cout << "Enter odd composite integer:" ;
	cin >> n;
	cout << "Do you want a complete trace of all steps (Y or N):" ;
	cin >> resp;

//  Will assume no trace if resp is not Y

//*********************************** Main Algorithm *************************************

x = int(sqrt(n)) + 1;
y = 0;

while (((x * x) - (y * y)) > n) 
{
  if (resp == 'Y')
  {
  cout << x << "  "  << y << endl;
  }
  y = y +1;
  if (((x * x) - (y * y)) < n)
  {
     x = x + 1;
     y = 1;
  }  
  else
  {if (((x * x) - (y * y)) == n)
    {
      a = x - y;
      b = x + y;
    }
  }
}

//*********************************** Output Total values ********************************

	cout << "Factors of " << n <<  " are: " << a << " and " << b << endl;
	
}