Codeforces 1333 F

题意： 给定大小为 $n$n的集合 $S$S， $n$n个元素为 $[1,n]$[1,n]中的元素且互不相同。
从中选择 $k$k个元素使得这 $k$k个元素的最大 $gcd$gcd最小，依次输出每个 $gcd$gcd， $k\in [2,n]$k∈[2,n]
题解：
首先筛出 $n$n内质数共 $cnt$cnt个，那么前 $cnt$cnt个答案就是 $1$1。
接下来的答案必定是 $2,3,\mathrm{4...}$2,3,4...
那么由于一个数 $x$x加入集合前，他的次大质因子 $prime$prime一定已经存在于集合之中。
如果 $prime$prime不存在，那么先加入 $x$x的答案不会比先加入 $prime$prime更优，故加入一个 $x$x后的 $gcd$gcd就是 $prime$prime。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 500010;
int pri[N], cnt, Mi_pri[N];
bool st[N];
int n;
vector<int> res; 
void xs() {
	st[0] = st[1] = true;
	for(int i = 2; i <= n; i++) {
		if(!st[i]) {
			pri[cnt++] = i;
			Mi_pri[i] = i;
		}
		
		for(int j = 0; j < cnt && i <= n / pri[j]; j++) {
			st[i * pri[j]] = true;
			Mi_pri[i * pri[j]] = pri[j];
			if(i % pri[j] == 0) break;
		}
	}
	for(int i = 2; i <= n; i++) res.push_back(i / Mi_pri[i]);
	sort(res.begin(), res.end());
	int len = res.size();
	for(int i = 0; i < len; i++) printf("%d%c", res[i], " \n"[i == len - 1]);
} 

int main()
{
	scanf("%d", &n);
	xs();
	return 0;		
}