思路：
- 筛选出<=n的素数
- 从大到小枚举这些素数的倍数
- 如果倍数个数是偶数，则任意匹配
- 如果倍数个数是奇数则留下2*p
- 最后枚举到2的倍数时，将之前剩下的加入一起匹配
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
int prime[N];//用来存储素数
int a[N];//a[i]=1表示i不是素数，a[i] = 0表示i是素数
int tot = 0;
typedef pair<int,int> PII;
typedef long long LL;
void get_prime(int n)//进行素数线性筛
{
tot = 0;
//找到[1,n/2]之间的素数
int m = n>>1;
for(int i=2;i<=m;i++)
{
if(a[i]) continue;
else
{
prime[tot++] = i;
//注意这里不能是int ，否则会爆数据，出现数组越界
for(LL j=i;j*i<=m;j++)
{
a[j*i] = 1;//质数i的倍数一定不是素数
}
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
memset(a,0,sizeof(a));
memset(prime,0,sizeof(prime));
get_prime(n);//进行素数线性筛
//从大到小排个序
sort(prime,prime+tot,greater<int>());
//下面用a数组来标记数字使用过没
memset(a,0,sizeof(a));
//cout<<tot<<endl;
vector<PII> ans;
vector<int> res;//如果某一次枚举时候 p的倍数个数是奇数，则存储2*p
//从大到小枚举素数
for(int i=0;i<tot;i++)
{
int p = prime[i];
//cout<<p<<" ";
vector<int> tmp;
//对于每一个素数，枚举他的倍数,存入tmp数组
for(int j=1;p*j<=n;j++)
{
if(!a[p*j])
{
a[p*j] = 1;
tmp.push_back(p*j);
}
}
//如果质数是2那么就把res数组里面的内容存入tmp数组
if(p==2)
{
for(int j=0;j<(int)res.size();j++)
{
tmp.push_back(res[j]);
}
}
if(((int)tmp.size()&1)&&(int)tmp.size()>2)
{
ans.push_back({
tmp[0],tmp[2]});
for(int j=3;j<(int)tmp.size()-1;j+=2)
{
ans.push_back({
tmp[j],tmp[j+1]});
}
res.push_back(tmp[1]);
}
else if((int)tmp.size()>=2)
{
for(int j=0;j<(int)tmp.size()-1;j+=2)
{
ans.push_back({
tmp[j],tmp[j+1]});
}
}
}
// cout<<endl;
printf("%d\n",(int)ans.size());
for(int i=0;i<(int)ans.size();i++)
{
printf("%d %d\n",ans[i].first,ans[i].second);
}
}
return 0;
}
细节收获：
在素数线性筛的时候枚举j，要开long long ,否则爆数据，数组越界
京公网安备 11010502036488号