/*
 * riddle.c - solves the riddle below.
 * Author: Jed Yang (htam)
 * Date: 2007.07.19
 *
 * The author heard the riddle from Matt Chan.  As follows:
 *
 * The number generator picks two integers that are bigger than 1.  He tells
 * the sum to player S, and tells the product to player P.  Upon some time
 * pondering, player S claims, "Neither of us know what the two integers are."
 * Then player P claims, "I know what the two integers are."  Then player S
 * claims, "So do I."
 *
 * Some clarifications.
 * Player S knows for certain, from the sum, that player P cannot possibly
 * know what the original numbers are.  He does not just say, "player P may
 * not know the numbers," but rather, he claims that "I know that player P
 * does not currently know what the numbers are."  After hearing this,
 * player P therefore deduce that "now that you said that, I know what the
 * two numbers are."  And player S follows by saying "now that you said that,
 * I also know what the two original numbers are."
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

/*
 * Increase this number to get more solutions.
 */
#define MAX 1000

char *primes = NULL;

/*
 * verbose determines the verbosity level of the program.  A bigger number
 * yields more text.  A negative verbosity will yield the same verbosity
 * as its absolute value when there is a solution; otherwise, it will be
 * like verbosity level 0.
 *
 * 5: analyze each product pairs
 * 4: tally results for each sum pair
 * 3: notice when sum pairs win
 * 2: summarize each sum
 * 1: test header and result
 * 0: one line for each test case
 */
int verbose = 0;

/*
 * init_primes initialize the primes array.  This should be called before
 * is_prime is ever called.
 *
 * argument: none.
 *
 * return value: none.
 *
 */
void init_primes(void)
{
   int i, j;
   int q, p;
   if (!(primes = (char *) calloc(MAX, sizeof(char))))
   {
      printf("cannot allocate memory\n");
      exit(EXIT_FAILURE);
   }
   
   for (i = 1; i < MAX; i++)
   {
      q = 2 * i + 1;
      p = 1;
      for (j = 1; j < i; j++)
      {
         if (q % (2 * j + 1) == 0)
         {
            p = 0;
            break;
         }
      }
      primes[i] = p;
   }
}

/*
 * is_prime checks whether a number is a prime.  It requires that init_primes
 * be called first to initialize the primes array.  It handles all inputs
 * safely and will exit the program if the prime is too large.
 *
 * argument: q - the query number.
 *
 * return value: 0 - not a prime.
 *               1 - is prime.
 *
 */
int is_prime(int q)
{
   if (q >= MAX * 2)
   {
      /*
       * This is the easiest way to limit the test cases so they only use
       * primality tests for those numbers that we have determined primality.
       * When we need to find out if a large number is prime, we simply exit
       * the program.
       */
      printf("is_prime: out of bound.\n");
      printf("exiting gracefully as intended.\n");
      exit(EXIT_SUCCESS);
   }
   if (q <= 1)
      return 0;
   if (q == 2)
      return 1;
   if (q % 2 == 0)
      return 0;
   return primes[(q - 1) / 2];
}

/*
 * guess_sum guess whether a sum S will yield the scenario that was described
 * in the problem statement.
 *
 * argument: s - the sum.
 *
 * return value: - 0 if the sum will not yield the scenario.
 *               - Z if (Z, S-Z) is will yield the scenario. 
 *
 */
int guess_sum(int s)
{
   int a, b, p, q, r, t, w, g, h, z;
   /*
    * Even after taking CS11 C track and being drilled about style, I still
    * prefer one letter variable names.  This is a very old ACM competition
    * style habit that I cannot shook.  However, I can give reasons to the 
    * names.
    *
    * a, b - the additive partition of the sum
    * p    - product of the sum pair
    * q, r - (incomplete) factorization of the product
    * t    - the test total of the product pair
    * w, g - the number of wrong and good factorizations
    * h    - the number of "Hooray" (see below)
    * z    - one of the two original numbers
    */

   if (verbose > 1) printf(" guessing that sum is %d\n", s);
   /*
    * When considering sum pairs (detailed below) in the eyes of player S,
    * whenever it yields a valid deduction for player P to be able to make
    * his claim, we say "Hooray" and increment H.
    *
    * If H is 1 after considering all the sum pairs, then player S can deduce
    * which sum pair when player P makes his claim.
    */
   h = 0;
   /*
    * Given the sum S, player S needs to think about all possible sum pairs
    * (A, B) such that A + B = S.  WLOG, A < B.  Also, we know a priori that
    * the product P = A * B has more than two factors.
    */
   for (a = 2; 2 * a < s; a++)
   {
      b = s - a;
      p = a * b;
      if (verbose > 2) printf("  analyzing sum pair (%d, %d) = %d\n", a, b, p);
      w = g = 0;
      /*
       * For each product P = A * B, we want to consider the different ways it
       * can be factored into Q * R = P.
       */
      for (q = 2; q * q < p; q++)
      {
         if (p % q == 0)
         {
            r = p / q;
            t = q + r;
            if (verbose > 4) printf("   analyzing product pair (%d, %d) = %d\n", q, r, t);
            /*
             * If the sum Q + R happens to be even or is a prime plus 2, then
             * when player S makes the first claim, player P can eliminate
             * this possible factorization.  Otherwise, it is retained.
             */
            if (t % 2 == 0 || is_prime(t-2))
               w++;
            else
               g++;
         }
      }
      if (verbose > 3) printf("  ruled out %d and retained %d\n", w, g);
      /*
       * If player P retains precisely one possible factorization, and since
       * a priori there are multiple factorizations, player P just ruled out
       * all but one and can now make his claim.
       */
      if (g == 1)
      {
         h++;
         if (verbose > 2) printf("  this is case %d where P can deduce: (%d, %d)\n", h, a, b);
         z = a;
         /*
          * For player S, if he sees multiple sum pairs that will give player
          * P the ability to make his claim, then when player P makes his
          * claim, player S cannot deduce which sum pair it is.
          */
         if (h > 1)
         {
            if (verbose > 1) printf(" P can deduce in multiple cases; so S cannot deduce the solution.\n");
            return 0;
         }
      }
   }

   /*
    * If after considering all sum pairs, there is precisely one sum pair that
    * yields a product where player P can deduce the original numbers, then
    * player S can deduce the original numbers after player P makes his claim.
    */
   if (h == 1)
   {
      if (verbose > 1) printf(" P can deduce in precisely one case; so S deduces as well: (%d, %d)\n", z, s - z);
      return z;
   }

   /*
    * It is also possible that none of the sum pairs admits a deduction by
    * player P.  In that case, the scenario does not hold.
    */
   if (verbose > 1) printf(" P cannot deduce in any case; so S cannot either.\n");
   return 0;
}

int main(void)
{
   int i, s, z;

   init_primes();

   for (i = 1; i < MAX; i++)
   {
      /*
       * Goldbach's Conjecture states that all composite even numbers can
       * be written as the sum of two prime numbers.
       *
       * Since Goldbach's Conjecture is open, and this program is designed
       * for small numbers, we will assume we cannot find a counter example
       * to Goldbach's Conjecture.  Therefore we assume that all positive
       * even numbers can be written as the sum of two primes.  This gives
       * an example where player S might think player P knows of a unique
       * factorization.  Therefore player S will not be able to say the
       * first claim.  When writing odd numbers as the sum of two primes,
       * we necessarily need to use the even prime number 2.  Therefore,
       * if we are given an odd number that is a prime number plus 2, then
       * player S cannot make the first claim.  Hence, the only cases we
       * need to examine is if the player S gets an odd number that is
       * a composite number plus 2.
       */
      if (!is_prime(2 * i + 1))
      {
         s = 2 * i + 3;
         if (verbose > 0) printf("%d is not prime, testing s=%d\n", s - 2, s);
         /*
          * Now we guess the sum is S, which is a composite number plus 2.
          * If the return number Z is nonzero, then it indicates that we
          * have a solution, and one of the number is Z.
          */
         if (z = guess_sum(s))
         {
            if (verbose < 0)
            {
               verbose *= -1;
               guess_sum(s);
               verbose *= -1;
            }
            printf("%d is a valid sum: (%d, %d)\n", s, z, s - z);
         }
         else
         {
            printf("%d fails.\n", s);
         }
      }
   }

   /*
    * This will actually never be reached, since is_prime will bail before
    * the for loop can let the counter run up to MAX.
    */
   return 0;
}