在做这道题之前，先了解一下欧拉筛：欧拉筛法的基本思想 ：在埃氏筛法的基础上（埃式筛法讲解可以阅读筛法--求1到100以内的素数），让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
代码：
1 int prime[maxn]; 2 int visit[maxn]; 3 void Prime(){ 4 mem(visit,0); 5 mem(prime, 0); 6 for (int i = 2;i <= maxn; i++) { 7 cout<<" i = "<<i<<endl; 8 if (!visit[i]) { 9 prime[++prime[0]] = i; //纪录素数， 这个prime[0] 相当于 cnt，用来计数 10 } 11 for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) { 12 // cout<<" j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl; 13 visit[i*prime[j]] = 1; 14 if (i % prime[j] == 0) { 15 break; 16 } 17 } 18 } 19 }
然后再来看这道题：最大公约数大于1，说明两个数不互质。而两个质数必然互质，两个合数不一定互不互质，一个质数只和他的倍数不互质。为了要求最大的匹配对数，我们可以用贪心的思想，把质数和他的倍数配对，而且我们知道一个数可以分解为几个质数相乘，所以我们只要找一遍所有<n/2的质数，就可以完成匹配。然后我们再考虑一个问题，配对必须是两两配对，所以当质数和他的倍数的个数之和为偶数，那么可以恰好配对，但如果个数之和为奇数，我们就需要考虑舍掉一个数，来完成两两配对，所以现在的问题就在于舍掉哪一个数。对于一个数，他可以由一个较大的质数*倍数但也可以由较小的质数*倍数，所以如果当前有一个数配不上对，我们就可以考虑到在一个更小的质数的情况下，能否配对。最小的质数为2，所以我们优先在奇数情况下，可以考虑把质数的两倍扔掉，一直到2，我们无路可退，那这个数必然配不上对。
代码如下(附注释)：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn=100005; 7 int n,prime[maxn >> 1],p[maxn],cnt; 8 int a[maxn], tmp, vis[maxn]; 9 int ans[maxn][2], ret; 10 inline void oula(int n){//欧拉筛 11 cnt = 0; 12 for(int i = 2; i <= n; ++i){ 13 if(!p[i]) 14 prime[++cnt] = i;//统计素数 15 for(int j = 1; j <= cnt && prime[j] * i <= n; ++j){ 16 p[prime[j] * i] = 1; 17 if(!(i % prime[j])) 18 break; 19 } 20 } 21 } 22 int main(){ 23 scanf ("%d",&n); 24 oula(n/2); 25 for(int i = cnt; i; --i){ 26 tmp = 0; 27 for(int j = prime[i]; j <= n; j += prime[i]) 28 if(!vis[j])//没有配过对 29 a[++tmp] = j;//记录素数的倍数 30 if(tmp & 1){//素数的倍数为奇数 31 swap(a[tmp], a[2]);//扔掉2倍 32 tmp--; 33 } 34 for(int j = 1; j <= tmp; j += 2){//配对 35 vis[a[j]] = vis[a[j + 1]] = 1;//标记已经配过对 36 ans[++ret][0] = a[j];//两个数的第一个数 37 ans[ret][1] = a[j + 1];//两个数的第二个数 38 } 39 } 40 printf("%d\n", ret); 41 for(int i = 1; i <= ret; ++i) 42 printf("%d %d\n", ans[i][0], ans[i][1]); 43 return 0; 44 }