rimes Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2844 Accepted Submission(s): 1277

Problem Description

Given a number n, please count how many tuple(p1, p2, p3) satisfied that p1<=p2<=p3, p1,p2,p3 are primes and p1 + p2 + p3 = n.

Input

Multiple test cases(less than 100), for each test case, the only line indicates the positive integer

Output

For each test case, print the number of ways.

Sample Input

3 9

Sample Output

0 2

题意：输入一个数字n，找出三个数字p1,p2,p3，满足p1<=p2<=p3并且p1+p2+p3=n

 1 //筛素数
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N = 10005;
 7 bool pri[N];
 8 int prime[N];
 9 int cnt;
10 void init()
11 {
12     cnt = 0;
13     pri[0] = pri[1] = 1;
14     for(int i = 2; i < N; i++)
15     {
16         if(!pri[i]){
17             prime[cnt++] = i;
18             for(int j = i+i; j < N; j+=i)
19             {
20                 pri[j] = 1;
21             }
22         }
23     }
24     return;
25 }
26 int main()
27 {
28     int n;
29     init();
30     while(~scanf("%d",&n))
31     {
32         int ans = 0;
33 
34         //printf("%d
",cnt);
35         for(int i = 0; i < cnt; i++)
36         {
37             if(3*prime[i]>n) break;
38             for(int j = i; j < cnt; j++)
39             {
40                 if(prime[i]+2*prime[j]>n) break;
41                 //for(int k = j; k < cnt; k++)
42                 //{
43                 //    if(prime[i]+prime[j]+prime[k]==n) ans++;// printf("%d %d %d
",prime[i],prime[j],prime[k]);printf("%d %d %d
",i,j,k);}
44                // }
45                if(!pri[n-prime[i]-prime[j]]) ans++;
46             }
47         }
48         printf("%d
",ans);
49     }
50     return 0;
51 }