1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6  7 const int maxn = 10005; 8 int prm[maxn / 3 + 1], is[maxn / 32 + 1]; 9 int n;10 int k;11 void get() {12     int N = maxn - 5;13     k = 0;14     for(int i = 2; i <= N; i++) {15         if(( is[i / 32] & ( 1 << ( i % 32 ) ) ) == 0) {16             prm[k++] = i;17         }18         for(int j = 0; j < k && prm[j] * i <= N; j++) {19             int num = prm[j] * i;20             is[num / 32] |= ( 1 << ( num % 32) );21             if(i % prm[j] == 0) {22                 break;23             }24         }25     }26 }27 bool check(int num) {28     int low = 0; int high = k - 1;29     while(low <= high) {30         int mid = ( low + high ) >> 1;31         if(prm[mid] >= num) {32             high = mid - 1;33         } else {34             low = mid + 1;35         }36     }37     if(num == prm[high + 1]) return true;38     return false;39 }40 41 int main() {42     while(scanf("%d",&n) && n) {43         get();44         int m = n / 2;45         if(!(n & 1)) m--;46         int ans = 0;47         for(int i = 0; prm[i] <= m; i++) {48             if(check(n - prm[i])) {49                 ans++;50 //                printf("%d %d\n", prm[i], n - prm[i]);51             }52         }53         printf("%d\n", ans);54     }55     return 0;56 }