Jzzhu has picked n apples from his big apple tree. All the apples are numbered from 1 to n. Now he wants to sell them to an apple store.
Jzzhu will pack his apples into groups and then sell them. Each group must contain two apples, and the greatest common divisor of numbers of the apples in each group must be greater than 1. Of course, each apple can be part of at most one group.
Jzzhu wonders how to get the maximum possible number of groups. Can you help him?
A single integer n (1 ≤ n ≤ 105), the number of the apples.
The first line must contain a single integer m, representing the maximum number of groups he can get. Each of the next m lines must contain two integers — the numbers of apples in the current group.
If there are several optimal answers you can print any of them.
6
2 6 3 2 4
9
3 9 3 2 4 6 8
2
0 题目大意：将编号为1~n的数两两分为一组，使得每组中的两个数gcd不为1，求最大组数. 分析：比较容易想到将数分为两大组.一组是2的倍数，一组是素数p以及p的倍数，在这两个互相制约的大组里选数拼起来.既然互相制约，那么就先分收益大的,这两个大组中的每两个数都可以拼成一个小组，如果先分第一个大组，那么第二个大组有的数就不能选，可能对于多个p组成的集合里面的数的个数都是奇数，性价比不高.所以先选第二个大组.对于每个质数p,现将p和p*3,p*4,.....这些数两两配对.如果最后还有一个数没有配对，就将它和p*2配对.这样第二大组的收益就最高了，接下来让第一大组尽量地分就好了. 至于为什么分成这样两个大组.一是要让每个分出来的大组中的任意两个数都能组成一个小组,满足题目给出的条件.二是这两个大组尽量不相交.除了2的质数都是奇数.一些偶数同时被分在两个大组是不可避免的，奇数如果不是质数，那么肯定存在于之前的一个质数p的集合中，否则就作为p.
#include#include #include #include using namespace std;int tot,n,prime[100010],tot2,vis[100010],a[100010],b[100010],cnt1,cnt2,tot3,notuse[100010];bool use[100010];struct node{ int x,y;} e[100010];void init(){ for (int i = 2; i <= n; i++) { if (!vis[i]) prime[++tot2] = i; for (int j = 1; j <= tot2; j++) { int t = prime[j] * i; if (t > n) break; vis[t] = 1; if (i % prime[j] == 0) break; } }}int main(){ scanf("%d",&n); init(); for (int i = 2; i <= tot2; i++) { memset(a,0,sizeof(a)); cnt1 = 0; a[++cnt1] = prime[i]; for (int j = 3; j * prime[i] <= n; j++) if (!use[j * prime[i]]) a[++cnt1] = j * prime[i]; if (2 * prime[i] <= n && !use[2 * prime[i]]) { if (cnt1 % 2 == 1) a[++cnt1] = 2 * prime[i]; else { use[2 * prime[i]] = 1; notuse[++tot3] = 2 * prime[i]; } } for (int j = 1; j + 1 <= cnt1; j += 2) { e[++tot].x = a[j]; e[tot].y = a[j + 1]; use[a[j]] = use[a[j + 1]] = 1; } } for (int i = 1; i * 2 <= n; i++) if (!use[i * 2]) notuse[++tot3] = i * 2; for (int i = 1; i + 1 <= tot3; i += 2) { e[++tot].x = notuse[i]; e[tot].y = notuse[i + 1]; } printf("%d\n",tot); for (int i = 1; i <= tot; i++) printf("%d %d\n",e[i].x,e[i].y); return 0;}