Q543: Goldbach's Conjecture

/*
   先算完全部，算質數的方法：用篩的(sieve)
   不用管even部分，因為這裡已經把質數除了2以外都是odd
   Run time: 0.090
*/
#include <stdio.h>
#define N 1000000
int main()
{
   int n;
   int i, j;
   bool arr[N+1];

   for ( i = 3; i < N; i+=2)
       arr[i] = true;

   for ( i = 3; i*i < N; i+=2)
       if (arr[i])
          for ( j = 3*i; j < N; j+=i)
              if (arr[j])
                 arr[j] = false;


   while (scanf("%d", &n))
   {
       if (!n) break;
       bool s = false;

       for ( i = 3; i <= n/2; i+=2)
       {
           if (arr[i])
           {
               j = n-i;
               if (arr[j])
               {
                   printf("%d = %d + %d\n", n, i, j);
                   s = true;
                   break;
               }
           }
       }
       if (!s)
          printf("Goldbach's conjecture is wrong\n");
   }
}