题目链接：uva 1434 - YAPTCHA

题目大意：给定n和k，求题目中给定的式子S(n)。

解题思路：威尔逊定理，x为素数时有，((x−1)!+1)%x==0，所以对于本题。假设3*k+7为素数的话，[(3k+6)!+1(3k+7−[(3k+6)!3k+7]]=1

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = 1e6;

int ans[maxn+5], vis[maxn*4+5];

void primeTable (int n) {

    memset(vis, 0, sizeof(vis));

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

        if (vis[i])

            continue;

        for (int j = 2 * i; j <= n; j += i)

            vis[j] = 1;

    }

}

int main () {

    primeTable(maxn*4);

    ans[1] = 0;

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

        ans[i] = ans[i-1] + (vis[3*i+7] ? 0 : 1);

    int cas, n;

    scanf("%d", &cas);

    while (cas--) {

        scanf("%d", &n);

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

    }

    return 0;

}