HDU 2098 分拆素数和

Time Limit: 1000/1000 MS (Java/Others)

Memory Limit: 32768/32768K (Java/Others)

【题目描述 - Problem Description】

　　把一个偶数拆成两个不同素数的和，有几种拆法呢？

【输入 - Input】	【输出 - Output】
输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。	对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。

【输入样例 - Sample Input】

【输出样例 - Sample Output】

【题解】

　　数据不大，能打表偷懒就打表偷懒吧，素数筛即可。

【代码 C++】

 1 #include <cstdio>
 2 #include <cstring>
 3 #define mx 10005
 4 int opt[mx];
 5 void rdy(){
 6     bool prim[mx];
 7     memset(prim, 0, sizeof(prim));
 8     prim[2] = 1;
 9     int i, j;
10     for (i = 3; i < mx; i += 2){
11         if (prim[i]) continue;
12         for (j = i << 1; j < mx; j += i) prim[j] = 1;
13     }
14     for (i = 3; i < mx; i += 2){
15         if (prim[i]) continue;
16         for (++opt[j = i + 2]; j < mx; j += 2){
17             if (!prim[j] && j + i < mx) ++opt[j + i];
18         }
19     }
20 }
21 int main(){
22     rdy();
23     int a;
24     while (scanf("%d", &a), a) printf("%d
", opt[a]);
25     return 0;
26 }