首先考虑一个问题:如果没有边数是素数的限制,应该怎么构造?
这其实很简单,把原图连成一个环即可,每个点度数为 \(2\)。
接着考虑在原图上加边,注意到 \(3\) 也是个素数,所以每次可以任意选两个度数为 \(2\) 的点连边,此时仍然符合条件。这样加边最多可以加 \(\left\lfloor\frac{n}{2}\right\rfloor\) 次。
这时就要用到一个定理:在 \(n\) 到 \(\left\lfloor\frac{3n}{2}\right\rfloor\) 中一定存在着一个素数 (证明太难了,我不会)。
其实可以手推一下,在 \(1000\) 以内两个相邻的素数的差最大也就 \(20\)(\(887\) 和 \(907\))。
所以只需依次加边,直到 \(m\) 是一个素数,此时新增的边的数量不超过 \(\left\lfloor\frac{n}{2}\right\rfloor\) 条。
代码中,我选的是每次连编号为 \(i\) 和 \(i+\left\lfloor\frac{n}{2}\right\rfloor\) 的边。
#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
int n,m;
bool f(int x)
{
for(int i = 2;i*i <= x;i++)
if(x%i==0)return 0;
return 1;
}
int main()
{
cin >> n;m = n;
while(!f(m))m++;
cout << m << endl;
for(int i = 1;i <= n;i++)printf("%d %d\n",i,i%n+1);
for(int i = 1;i <= m-n;i++)printf("%d %d\n",i,i+n/2);
return 0;
}
标签:Prime,lfloor,right,frac,题解,rfloor,素数,Graph,left
From: https://www.cnblogs.com/max0810/p/18329598