hdu 5104 素数打表水题

时间：2022-05-08 05:48:56

http://acm.hdu.edu.cn/showproblem.php?pid=5104

找元组数量，满足p1<=p2<=p3且p1+p2+p3=n且都是素数

不用素数打表都能过，数据弱的一比

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <map>

#include <iostream>

#include <sstream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define clr0(x) memset(x,0,sizeof(x))

#define clr1(x) memset(x,-1,sizeof(x))

#define eps 1e-9

const double pi = acos(-1.0);

typedef long long LL;

const int inf = 0x7fffffff;

const int maxn = 1e5+5;

int p[maxn],pr[maxn],cnt = 0;

int n;

void init()

{

    clr0(p);

    for(int i = 2;i < maxn;++i){

        if(!p[i]){

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

                p[j] = 1;

        }

    }

    p[0] = 1;

    for(int i = 2;i < maxn;++i)

        if(!p[i])

            pr[cnt++] = i;

}

int main()

{

    init();//cout<<cnt;

    while(~RD(n)){

        LL ans = 0;

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

            if(n < pr[i]*3)

                break;

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

                int k = n - pr[i] - pr[j];

                if(pr[j] > k)

                    break;

                //printf("%d %d %d \n",pr[i],pr[j],k);

                if(!p[k])

                    ans++;

            }

        }

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

    }

    return 0;

}

相关文章