方法1：模拟 Alice 筛法（TLE）

根据题意模拟即可（注意：真因数指不包括 $n$ 的所有 $n$​ 的因数）。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void solve() 
{
    int n;
    cin>>n;
    vector<bool>vis(n+1,false);//真因数
    int p=n;
    while(p>1) 
    {
        for(int i=1;i*i<=p;i++) //标记真因数
        {
            if(p%i==0) 
            {
                vis[i]=true;
                if(i!=1&&i!=p/i) 
                    vis[p/i]=true;
            }
        }
        int q=-1;
        for(int i=p-1;i>=2;i--) 
            if(!vis[i]) 
            {
                q=i;//有被标记的数
                break;
            }
        if(q==-1)break; 
        p=q;//没有被标记的数
    }
    int count=0;//统计数量
    for(int i=2;i<=n;i++) 
    {
        if(!vis[i]) 
            count++;
    }
    cout<<count<<endl;
}
signed main() 
{
    int T;
    cin>>T;
    while(T--) 
        solve();
    return 0;
}

但是提交后发现 TLE 了，说明有一定的规律可循。

方法2：找规律（AC）

题目要求：

1. 创建序列：从 $n$ 到 $2$ 的严格下降序列。
2. 初始化：令 $P=n$。
3. 标记真因数：标记 $P$ 的所有真因数（不包括 $P$ 本身）。
4. 寻找下一个 P：找到从 $P-1$ 到 $2$ 中最大的未被标记的数 $q$，令 $P = q$。
5. 重复：如果 $q$ 存在，重复步骤 $3$ 和 $4$，否则停止。

关键：

1. 标记真因数：每次标记 $P$ 的真因数时 $P$ 本身不会被标记。
2. 寻找下一个 P：每次找到的 $P$ 都是当前未被标记的数中最大的一个。

结果：

• $n$ 为偶数时：最后一次选 $P$ 时，$P$​ 正好处于 $\frac{n-2}{2}$。
• $n$ 为奇数时：最后一次选 $P$ 时，$P$ 正好处于 $\frac{n-2}{2}-1$。

所以：

未被标记的数（即答案）则为 $\lfloor \frac{n+1}{2} \rfloor$。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<floor((n+1)/2)<<endl;
    }
    return 0;
}