本文共 1477 字，大约阅读时间需要 4 分钟。

题目

思路

超级神奇$の$构造大法。

首先扔掉大于 $\lfloor \frac{n}{2}\rfloor$ 的素数，因为他们不可能匹配。

对于每个奇素数，把所有的倍数拿来两两匹配。非得剩下一个咋办？剩下 $2p$ 。

最后，我们获得了一堆 $2p$ ，和一个 $1$ 。继续两两匹配即可。

显然这是理论最大值，因为 $1$ 本身就不能匹配，相当于最多只剩下一个 $2p$ 。

老板娘，怎么没数字了？只剩一个数字，让我怎么配对？

代码

#include <cstdio>#include <iostream>#include <algorithm>#include <vector>using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}template < typename T >void getMax(T&a,const T&b){   if(a<b)a=b;}template < typename T >void getMin(T&a,const T&b){   if(b<a)a=b;}const int MaxN = 100015;vector< int > v;bool used[MaxN], isPrime[MaxN];int main(){   	int n = readint();	for(int i=2; i<=n; ++i)		isPrime[i] = true;	for(int i=2; i*i<=n; ++i)		if(isPrime[i]){   			for(int j=i*i; j<=n; j+=i)				isPrime[j] = false;		}	int tot = 0;	for(int i=2; i<=n; ++i)		if(!isPrime[i] || i <= n/2)			++ tot;	printf("%d\n",tot>>1);	for(int i=(n>>1); i>2; --i){   		if(!isPrime[i]) continue;		int last = -1;		for(int j=n/i; j>=1; --j){   			if(used[i*j]) continue;			used[i*j] = true;			if(~last && j == 2){   				v.push_back(i*j);				continue;			}			if(last == -1)				last = i*j;			else{   				printf("%d %d\n",last,i*j);				last = -1;			}		}	}	for(int i=1; i<=(n>>1); ++i)		if(!used[i<<1])			v.push_back(i<<1);	for(int i=0,len=v.size(); i+1<len; i+=2)		printf("%d %d\n",v[i],v[i+1]);	return 0;}