显然我们只要考虑小于等于 $n/2$ 的质数
对于每个不为 $2$ 的质数 $p$ ，如果目前它的还没匹配的倍数有偶数个，那么显然这些都可以匹配完
否则，如果有奇数个，那么我们把 $2p$ 留着不匹配，剩下偶数个拿来全部匹配
最后剩下的数都是 $2$ 的倍数，一个个匹配即可，如果剩下奇数个只能留一个没法匹配了
显然这样是匹配数的上界
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7; int n; bool vis[N]; vector <pair<int,int>> V; inline void ins(int x,int y) { vis[x]=vis[y]=1; V.push_back(make_pair(x,y)); } int pri[N],tot; bool not_pri[N]; void pre() { not_pri[1]=1; for(int i=2;i<=n;i++) { if(!not_pri[i]) pri[++tot]=i; for(int j=1;j<=tot;j++) { ll g=1ll*i*pri[j]; if(g>n) break; not_pri[g]=1; if(i%pri[j]==0) break; } } } int main() { n=read(); pre(); vector <int> rem;// rem.push_back(2); for(int i=2;i<=tot&&pri[i]<=n/2;i++) { vector <int> tmp; int t=pri[i]; for(int j=t;j<=n;j+=t) if(!vis[j]) tmp.push_back(j); int sz=tmp.size(); if(sz&1) { ins(tmp[0],tmp[2]); rem.push_back(tmp[1]); vis[tmp[1]]=1; for(int j=3;j<sz;j+=2) ins(tmp[j],tmp[j+1]); } else for(int j=0;j<sz;j+=2) ins(tmp[j],tmp[j+1]); } for(int i=2;i<=n;i+=2) if(!vis[i]) rem.push_back(i); int sz=rem.size(); for(int i=1;i<sz;i+=2) ins(rem[i],rem[i-1]); printf("%d\n",int(V.size())); for(auto A: V) printf("%d %d\n",A.first,A.second); return 0; }