题目：

官方题解：

如果答案是1，就需要猜质数次；把质数分组，一组一组猜就行了。一组就是最大的一个和最小的几个匹配。

然而既不知道为什么这样是最坏情况，也不知道为什么最大的一个和最小的几个匹配一定最优。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=1e4+5;int n,pri[N],cnt,ans;bool vis[N];int main(){  scanf("%d",&n);  for(int i=2;i<=n;i++)    {      if(!vis[i])pri[++cnt]=i;      for(int j=1;j<=cnt&&i*pri[j]<=n;j++)    {      vis[i*pri[j]]=1;      if(i%pri[j]==0)break;    }    }  int p0=1;  for(int i=cnt;i;i--)    {      if(p0>i)break;      ans++;int ml=pri[i];      while(ml*pri[p0]<=n&&p0