题解 | #素数三元组#

数论简单知识,不多bibi

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
[[maybe_unused]]const int INF = 1e16 + 50, N = 1e6 + 50;
[[maybe_unused]] typedef std::pair<int, int> pii;
int a[N], primes[N], pos;
bool f[N];

void pre() {
    for (int i = 2; i < N; i++) {
        if (!f[i]) primes[pos++] = i;
        for (int j = 0; primes[j] * i < N; j++) {
            f[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
    for (int i = 0; i < pos; i++)
        if (!f[primes[i] + 2])
            a[primes[i] + 2] = 1;
    for (int i = 1; i < N; i++)
        a[i] += a[i - 1];
}

void solve() {
    int n;
    std::cin >> n;
    std::cout << a[n] << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    pre();
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve();
    return 0;
}