link，感觉这道题目质量挺高的，洛谷上没有这道题目，故想要搬运过去，但是本人太菜，不会造数据 qwq，希望巨佬帮帮忙。
注意：本题使用 SPJ，具体要求请看说明提示，并且输出格式中：
之后 n-1 行，每行输出两个以空格隔开的正整数 u,v，表示最小生成树的一条边的两个端点。
这里输出的边没有顺序，端点也没有顺序。
比如：样例输出：
7
1 2
1 3
2 4
这样输出也是对的：
7
2 1
1 3
2 4
这样输出也是对的：
7
1 3
1 2
2 4
标程放在这里：
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
#define i_will signed
#define ak main
#define IMO ()
#define int long long
#define double long double
I AK IOI;
const int MAXN=3e6+5;
int p[MAXN],n,sum;
vector<int>pp;
vector<pair<int,int> >g;
void solve(int n) {
for(int i=2;i<=n;i++){
if(!p[i]){
p[i]=i;
pp.push_back(i);
}
for(int it:pp){
if(i*it>n)break;
p[i*it]=it;
if(i%it==0)break;
}
}
}
i_will ak IMO{
cin>>n;
solve(n);
for(int i=2;i<=n;i++){
int p_=p[i];
int j=i/p_;
sum+=p_;
g.push_back({j,i});
}
cout<<sum<<endl;
for(auto it:g)cout<<it.first<<' '<<it.second<<endl;
i_ak ioi;
}
悬赏解决方案一个，并且洛谷三关 or 大号互关。