数的集合 - 非正经题解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e6 + 5;
int p[maxn], cnt;
bitset<maxn> _p;
int pre[maxn];  
void sieve()
{
    _p.set();
    _p[0] = _p[1] = false;
    pre[1] = 0;
    for (int i(2); i < maxn; ++i)
    {
    if (_p[i]) p[cnt++] = i;
    for (int j(0); j < cnt && i * p[j] < maxn; ++j)
    {
    _p[i * p[j]] = false;
    if (i % p[j] == 0) break;
    }
    pre[i] = pre[i - 1] + (_p[i]? 1 : 0);  
    }
}
int solve(int n)
{
    if (_p[n]) return 0;  
    return (n - 2) - (pre[n - 1] - pre[n / 2]);
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(NULL); 
    sieve();
    int t;
    cin >> t;
    while (t--)
    {
    int n;
    cin >> n;
    cout << solve(n) << '\n'; 
    }
}

可用线性筛找所有素数，同时计算前缀和 $pre[i]$ (表示前 $i$ 个数字里的素数数) 。

• 若 $n$ 是素数，直接输出 $0$ 即可。
• 若 $n$ 非素数，显然要计算小于 $n$ 且能与 $n$ 合到同一集合的元素数。显然得排除在区间 $[n / 2, n]$ 内的素数数
  即用 $n - 2$ (排除 $1$ 和 $n$ 本身)，再减去在区间 $[n / 2, n]$ 的素数数 $pre[n - 1] - pre[n / 2]$ 即可。

时间复杂度 $O(maxn + t)$。
目前提交记录用时最优解