题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2632
官方题解：http://neerc.ifmo.ru/archive/2011/neerc-2011-analysis.pdf
但还是不懂；
如果猜1是最坏情况，那么其它数怎么用更少的次数猜到？
为什么和大质数配对的小质数是连续的？比如 2*3 > 5，那么也有可能会跳着选啊？
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int const xn=1e5+5; int n,cnt,pri[xn]; bool vis[xn]; void init() { for(int i=2;i<=n;i++) { if(!vis[i])pri[++cnt]=i; for(int j=1;j<=cnt&&(ll)i*pri[j]<=n;j++) { vis[i*pri[j]]=1; if(i%pri[j]==0)break; } } } int main() { scanf("%d",&n); init(); int p=1,ans=0; for(int i=cnt;i>=p;i--) { int nw=pri[i]; while(p<i&&(ll)nw*pri[p]<=n)nw*=pri[p],p++; ans++; } printf("%d ",ans); return 0; }