/*
This program computes the solution to this riddle:

----
Two integers, m and n, each between 2 and 100 inclusive, have been
chosen. The product, mn, is given to mathematician X.
The sum, m + n, is given to mathematician Y. Their conversation is as
follows:

X: I don't have the foggiest idea what your sum is, Y.

Y: That's no news to me, X. I already knew that you didn't know.

X: Ahah, NOW I know what your sum must be, Y!

Y: And likewise X, I have surmised your product !!

Find the integers m and n.
----

In this program, the maximum value of the integers m and n is not fixed as 100, but is chosen by the user.

Note:
1. I dont know the "correct" way of solving this riddle, this is my way
2. The program could have been coded in a more efficient way. I just wanted to get the answers hence this inefficient coding.

-Gaurang Khetan (http://gaurang.org)

*/

#include <stdio.h>

//  define the following if you are compiling for windows
//  in a windows compile, the program will prompt for a Enter keypress before ending
//  so that the program window does not close immediately as the program displays the solution
//#define WINDOWS_COMPILE  

int main()
{
  void end_of_prog();
  int max;

  /* take input */
  do
    {
      printf("Enter maximum possible value of the integers m and n (5 to 2000, typically 100): ");
      scanf("%d", &max); 
      fflush(stdin); //scanf() does not eat the enter key character
    }
  while (max > 2000 || max < 5);       // 2000 requires around 16MB prod array, more than 2000 would require HUGE memory
  
  /* allocate memory required for computation */
  int* prod = new int[max*max+1];
  int* sum = new int[max+max+1];
  if (prod==NULL || sum==NULL)
    {
      printf("\n INSUFFICIENT MEMORY!!\n");
      end_of_prog();
      return 1;
    }
  
  /* start computing */
  printf("\nComputing...may take some time...");
  int i,j;
  prod[0] = prod[1] = prod[2] = prod[3] = sum[0] = sum[1] = sum[2] = sum[3] = 0; //impossible

  //process sentence 1
  for (i=4; i<=max*max; i++) 
    prod[i] = 1;  //mark as unvisited yet

  for (i=2; i<=max; i++)
    for (j=i; j<=max; j++)
      {
	if (prod[i*j] == 1)
	  prod[i*j] = i+j; //first time
	else 
	  { //non-first time
	    if (prod[i*j] != 0) //not yet assigned as having non-unique sums
	      if (i+j != prod[i*j])
		prod[i*j] = 0;     //it has non-unique possible sums
	  }
      }

  for (i=0; i<=max*max; i++) 
    prod[i] = ( (prod[i]==0)? 1 : 0 );  //only those with non-unique possible sums are possible in this riddle
                                        //those with unique possible sums and the unvisited ones are not possible
      
  //process sentence 2
  for (i=4; i<=max+max; i++)
    {
      sum[i] = 1;
      for (j=2; j<=i/2; j++)
	if (prod[j*(i-j)] == 0)
	  {
	    sum[i] = 0;  //not possible in this riddle, since it has a possible product with unique possible sum
	    break;
	  }
    }
  
  //process sentence 3
  for (i=2; i<=max; i++)
    for (j=i; j<=max; j++)
      if (prod[i*j] != 0 && sum[i+j] == 1)
	{
	  if (prod[i*j] == 1)
	    prod[i*j] = i+j; //it has one possible sum
	  else if (i+j != prod[i*j])
	    prod[i*j] = 0;     //it has multiple possible non-unique sums
	}

  for (i=0; i<=max*max; i++) 
    prod[i] = ( (prod[i]>1)? 1 : 0 );  //only those with ONE unique possible sum are possible in this riddle
                                        //those with none or more than one unique possible sums are not possible

  //process sentence 4
  for (i=4; i<=max+max; i++)
    if (sum[i] != 0)
      {
	int count = 0;
	for (j=2; j<=i/2; j++)
	  if (prod[j*(i-j)] == 1)
	    count++;
	if (count!=1)
	  sum[i] = 0;  //not possible in this riddle, only those with ONE unique possible product are possible in this riddle
      }

  /* print the solutions */
  printf("done.\n\nSolutions: \n");

  for (i=4; i<=max+max; i++)
    if (sum[i] == 1)
      for (j=2; j<=i/2; j++)
	if (prod[j*(i-j)] == 1)
	  printf("m & n = %d & %d; X:mn=%d; Y:m+n=%d\n", j, i-j, j*(i-j),i);
  
  printf("\nSolution Complete.\n\n");
  
  /* end */
  delete [] prod;
  delete [] sum;
  end_of_prog();
  return 0;
}

void end_of_prog()
{ 
#ifdef WINDOWS_COMPILE
  char str[10];
  printf("\n Press the enter key to terminate...");
  fgets(str, 10, stdin);
#endif
}