题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5104

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 n(n≤10000).

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

 //筛素数

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = ;

 bool pri[N];

 int prime[N];

 int cnt;

 void init()

 {

     cnt = ;

     pri[] = pri[] = ;

     for(int i = ; i < N; i++)

     {

         if(!pri[i]){

             prime[cnt++] = i;

             for(int j = i+i; j < N; j+=i)

             {

                 pri[j] = ;

             }

         }

     }

     return;

 }

 int main()

 {

     int n;

     init();

     while(~scanf("%d",&n))

     {

         int ans = ;

         //printf("%d\n",cnt);

         for(int i = ; i < cnt; i++)

         {

             if(*prime[i]>n) break;

             for(int j = i; j < cnt; j++)

             {

                 if(prime[i]+*prime[j]>n) break;

                 //for(int k = j; k < cnt; k++)

                 //{

                 //    if(prime[i]+prime[j]+prime[k]==n) ans++;// printf("%d %d %d\n",prime[i],prime[j],prime[k]);printf("%d %d %d\n",i,j,k);}

                // }

                if(!pri[n-prime[i]-prime[j]]) ans++;

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

hdu_5104 Primes Problem()

rimes Problem

最新文章

热门文章