Bestcoder round 18---A 문제(소수 체+소수 타 표+세 개의 소수 와 그 합 을 찾 습 니 다=n)

Primes Problem
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 12    Accepted Submission(s): 11
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
 
Accepted 코드:
 

#include <string>

#include <iostream>

#include <cstdio>

#include <math.h>

#include <cstring>

#include <algorithm>

#include <queue>



using namespace std;



int f[10001];



void sushu()

{

    int i, j;

    memset(f, 0, sizeof(f));

    f[1]=1;

    i=2;

    while(i<=200)

    {

        for(j=i*2; j<=10000; j+=i)

        {

            f[j]=1;

        }

        i++;

        while(f[i]==1)

        {

            i++;

        }

    }

}



int s[10000], e;



int main()

{

    int n;

    int i, j, k;

    int cnt;

    sushu();

     e=0;

    for(i=2; i<=10000; i++)

    {

        if(f[i]==0)

        {

            s[e++]=i;

        }

    }

    while(scanf("%d", &n)!=EOF)

    {

        if(n<6)

        {

            cout<<'0'<<endl;

            continue;

        }

        cnt=0;

        int flag=0;

        for(i=0; i<=n; i++)

        {

            if(s[i]>=n)

              break;

            for(j=i; j<=n; j++)

            {

                if( (s[i]+s[j])>=n )

                {

                    flag=1;

                    break;

                }

                else

                {

                    int dd=n-s[i]-s[j];

                    if(f[dd]==0 && dd>=s[i] && dd>=s[j] )

                    {

                        cnt++;

                    }



                }

            }

        }

        cout<<cnt<<endl;

    }

    return 0;

}

 
 
이 코드 는 시간 이 초과 되 었 습 니 다(3 층 순환 이 너무 오래 걸 립 니 다).

#include <string>

#include <iostream>

#include <cstdio>

#include <math.h>

#include <cstring>

#include <algorithm>

#include <queue>



using namespace std;



int f[10001];



void sushu()

{

    int i, j;

    memset(f, 0, sizeof(f));

    f[1]=1;

    i=2;

    while(i<=200)

    {

        for(j=i*2; j<=10000; j+=i)

        {

            f[j]=1;

        }

        i++;

        while(f[i]==1)

        {

            i++;

        }

    }

}



int s[10000], e;



int main()

{

    int n;

    int i, j, k;

    int cnt;

    sushu();

     e=0;

    for(i=2; i<=10000; i++)

    {

        if(f[i]==0)

        {

            s[e++]=i;

        }

    }

    while(scanf("%d", &n)!=EOF)

    {

        if(n<6)

        {

            cout<<'0'<<endl;

            continue;

        }

        cnt=0;

        for(i=0; i<=n; i++)

        {



            for(j=i; j<=n; j++)

            {

                for(k=j; k<=n; k++)

                {

                    if((s[i]+s[j]+s[k])==n)

                    {

                        cnt++;

                    }

                }

            }

        }

        cout<<cnt<<endl;

    }

    return 0;

}