G15 威尔逊定理

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1000001;
const int mx = 3000008;
int s[N], p[N], vis[mx], t, n;

void get_prim()
{
    for (LL i = 2; i < mx; ++i)
        if (!vis[i])
        {
            if ((i - 7) % 3 == 0)
                p[(i - 7) / 3] = 1;
            for (LL j = i * i; j < mx; j += i)
                vis[j] = 1;
        }
}
int main()
{
    get_prim();
    for (int i = 2; i < N; ++i)
        s[i] = s[i - 1] + p[i];
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        printf("%d\n", s[n]);
    }
    return 0;
}

G15 威尔逊定理

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1000001;
const int mx = 3000008;
int s[N], p[N], vis[mx], t, n;

void get_prim()
{
    for (LL i = 2; i < mx; ++i)
        if (!vis[i])
        {
            if ((i - 7) % 3 == 0)
                p[(i - 7) / 3] = 1;
            for (LL j = i * i; j < mx; j += i)
                vis[j] = 1;
        }
}
int main()
{
    get_prim();
    for (int i = 2; i < N; ++i)
        s[i] = s[i - 1] + p[i];
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        printf("%d\n", s[n]);
    }
    return 0;
}