喵哈哈村的狼人杀大战(4)

描述

喵哈哈村最近热衷于玩一个叫做狼人杀的游戏！

徐元帅同学今天他抽到的是女巫的身份，按照他的一贯玩法，他喜欢一开始就把自己毒死。

于是他早早的就出去了。

他很无聊，于是出了一道题给自己玩。

他从怀里面掏出了一个数字n。

他想知道有多少组三元组(a,b,c)，满足a<=b<=c，且a,b,c都是素数，而且a+b+c=n。

输入

本题包含若干组测试数据。
每组测试数据只含有一个整数n。
1<=n<=10000

输出

输出三元组的数量。

样例输入1

3
9

样例输出1

0
2
题解

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10000;
int np, pri[maxn+5], vis[maxn+5];
void prime_table(int n) {
    np = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (vis[i])
            continue;
        pri[np++] = i;
        for (int j = i * i; j <= n; j += i)
            vis[j] = 1;
    }
}
int main () {
    int n;
    prime_table(maxn);
    while (scanf("%d", &n) == 1) {
        int ans = 0;
        for (int i = 0; i < np; i++) {
            for (int j = i; j < np; j++) {
                if (pri[i] + pri[j] >= n)
                    break;
                int t = n - pri[i] - pri[j];

                if (vis[t] == 0 && t >= pri[j])
                    ans++;
            }
        }
        printf("%d
", ans);
    }
    return 0;
}