读懂题之后发现条件一和条件二并没有什么用

然后对于条件四显然可以将整个图连成一个环

然后考虑条件三怎么满足？

假如点数正好是质数，直接就满足了

否则

此时所有点的度数都是2。

给每个点多连一条边，度数依然是质数

发现这样最多可以连\(\lfloor \frac{n}{2} \rfloor\)条边，1000以内的合数与最近的质数没有超过\(\lfloor \frac{n}{2} \rfloor\)的，所以枚举一下质数，直接连就行了

代码：

#include
    
     #include
     
      #include
      
       using namespace std;#define rg registervoid read(int &x){    char ch;bool ok;    for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}const int maxn=1110,N=1100;int n,pri[maxn],tot,m;bool vis[maxn];void prepare(){    vis[1]=1;    for(rg int i=2;i<=N;i++){    if(!vis[i])pri[++tot]=i;    for(rg int j=1;j<=tot&&pri[j]*i<=N;j++){        vis[pri[j]*i]=1;        if(i%pri[j]==0)break;    }    }}int main(){    read(n),prepare();    if(!vis[n]){    printf("%d\n",n);    for(rg int i=1;i