#include <stdio.h>
#include <stdlib.h>

#define LIMIT 1000000

char *isPrime = NULL;
int *prime = NULL;
int *nways = NULL;

int getAllPrimes ( )
{
   int i, j, cnt;

   isPrime[0] = isPrime[1] = 0;
   for (i=2; i<=LIMIT; ++i) isPrime[i] = 1;
   i = 2; cnt = 0;
   while (i <= LIMIT) {
      if (isPrime[i]) {
         ++cnt;
         j = 2 * i;
         while (j <= LIMIT) {
            isPrime[j] = 0;
            j += i;
         }
      }
      ++i;
   }
   return cnt;
}

int printways ( int n )
{
   int i, cnt;

   if (n % 2) return 0;
   i = 3; cnt = 0;
   while (i <= n / 2) {
      if (isPrime[i] && isPrime[n-i]) {
         ++cnt;
         printf("= %d + %d\n", i, n-i);
      }
      i += 2;
   }
   return cnt;
}

int main ()
{
   int i, j, n, np, max, maxn;

   /* Status of all integers up to limit */
   isPrime = (char *)malloc((LIMIT + 1) * sizeof(char));
   np = getAllPrimes();
   printf("Number of primes = %d\n", np);

   /* Store only the primes */
   prime = (int *)malloc(np * sizeof(int));
   for (n=i=0; i<=LIMIT; ++i) if (isPrime[i]) prime[n++] = i;
   printf("Number of primes stored = %d\n", n);

   /* Generate the counts of sum possibilities */
   nways = (int *)malloc((LIMIT + 1) * sizeof(int));
   for (i=0; i<=LIMIT; ++i) nways[i] = 0;
   for (i=1; i<=np; ++i) {
      for (j=i; j<=np; ++j) {
         n = prime[i] + prime[j];
         if (n > LIMIT) break;
         ++nways[n];
      }
   }

   max = 0; maxn = 4;
   for (n=6; n<=LIMIT; n+=2) {
      if (nways[n] > max) {
         max = nways[n];
         maxn = n;
      }
   }
   printf("%d\n", maxn);
   printways(maxn);
   printf("Total number of ways = %d\n", max);

   /* free memory */
   free(isPrime);
   free(prime);
   free(nways);

   exit(0);
}