meepo's Blog

6

2
6 3
2 4

9

3
9 3
2 4
6 8

2

0

    也是一道比较傻的贪心。。。我就奇怪了。。为什么我挑的都是这种题。。好不容易鼓起勇气打了一场Div1。。然后碰到两道贪心这样真的好吗、、、

    具体的思路是。。先把素数筛出来。。然后处理出每一个数的素因数有多少个和每一个素数的倍数。。

然后从大到小枚举素数。。从素数的倍数里找两个数，计入答案。。找数的原则是先找素因数少的数。。因为这样显然比较优嘛。。好吧其实是我不会证。。。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct data{int x,y;} Ans[50010];
vector <int> a[50010];
int n,ans,vis[100100],pri[50010],sum[100010],Sum,fis,tot,v[100010];
bool cmp(int a,int b){
	if (sum[a]==sum[b]) return a<b;
	return sum[a]<sum[b];
}
void Getpri(){
	for (int i=2;i<=n;i++){
		if (!v[i]) pri[++Sum] = i;
		for (int j=1;i*pri[j]<=n && j<=Sum;j++){
			v[pri[j]*i] = 1;
			if (!(i%pri[j])) break;
		}
	}
}
int main(){
	scanf("%d",&n);
	Getpri();
	for (int i=1;i<=Sum;i++)
		for (int j=1;pri[i]*j<=n;j++) a[i].push_back(pri[i]*j),sum[pri[i]*j]++;
	for (int i=Sum;i;i--){
		sort(a[i].begin(),a[i].end(),cmp);tot = 0;
		for (int j=0;j<a[i].size();j++)
			if (!vis[a[i][j]]){
				if (tot==1){
					Ans[++ans] = (data){fis,a[i][j]};
					vis[a[i][j]] = vis[fis] = 1;
					tot = 0;
				}
				else {tot = 1;fis = a[i][j];}
			}
	}
	printf("%d\n",ans);
	for (int i=1;i<=ans;i++) printf("%d %d\n",Ans[i].x,Ans[i].y);
}