Computer Programming Contest Preparation

    1 #include <iostream>
    2 
    3 const long int SIZE = 1000001;
    4 long int prime[SIZE];
    5 long int ans[SIZE];
    6 
    7 void compute_prime()
    8 {
    9     long int count = 0;
   10     for(int x = 0; x < SIZE; x++)
   11         {
   12             prime[x] = x;
   13         }
   14     prime[1] = 0;
   15     for(long int x = 2; x < SIZE; x++)
   16         {
   17             for(long int y = x; x*y < SIZE && x*y >= 0; y++)
   18                 {
   19                     prime[(long long)x*y] = 0;
   20                 }
   21         }
   22 }
   23 long int test(long int i)
   24 {
   25     long int ret = 0;
   26     long int j = 3;
   27     while(0 == ret)
   28         {
   29             if(0 != prime[j])
   30                 {
   31                     if(0 != prime[i-j])
   32                         {
   33                             ret = j;
   34                         }
   35                 }
   36             j += 2;
   37         } //END WHILE
   38     return ret;
   39 }
   40 
   41 void compute()
   42 {
   43     for(long int i = 6; i < SIZE+1; i+=2)
   44         {
   45             ans[i] = test(i);
   46         }
   47 }
   48 int main()
   49 {
   50     compute_prime();
   51     compute();
   52     long int input;
   53     std::cin >> input;
   54     while(0 != input)
   55         {
   56             std::cout << input << " = " << ans[input] << " + " << input-ans[input] << std::endl;
   57             std::cin >> input;
   58         }
   59     return 0;
   60 }
   61