分拆素数和（在线操作）

showproblem.php?pid=2098

hdu:2098:分拆素数和

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 27221 Accepted Submission(s): 11915

Problem Description

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

Input

输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。

Output

对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。

Sample Input

30 26 0

Sample Output

3 2

Source

2007省赛集训队练习赛（2）

题解：刚开始犯了一个致命的错误，没有看清这个题特意给出的数据范围，因为打表一定会超时的？？所以在线操作就可以了，用筛法求素数

 1 #include<cstdio>
 2 #include<cstring>
 3 /*int IsPrime(int n)
 4 {
 5     int i;
 6     for (i=2; i<=sqrt(n); i++)
 7     {
 8         if (n % i == 0)
 9             return 0;
10     }
11     return 1;
12 }
13 */
14 #define N 10010
15 bool b[N];
16 void pri()
17 {
18     memset(b,0,sizeof(b));
19     for(int i = 2 ;i < N ;i++)
20     {
21         if(b[i]==0){
22             for(int j = i*i ; j < N ;j+=i)
23                 b[j] = 1;
24         }
25     }
26 }
27 int main()
28 {
29     int n, i, cnt;
30     pri();
31     while (scanf("%d", &n) && n)
32     {
33         cnt = 0;
34         for (i=3; i<n/2; i+=2)
35         {//因为是不同的两个素数，那必定一个比n/2大，一个比n/2小
36             if ( b[i]==0 && b[n-i]==0 )
37                 cnt++;
38         }
39         printf("%d
", cnt);
40     }
41     return 0;
42 }