大素数表+二分
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 ", prm[i], n - prm[i]); 51 } 52 } 53 printf("%d ", ans); 54 } 55 return 0; 56 }