算法一

由于本质不同点的个数比最优解少没有分，我们考虑先最大化本质不同点的个数（

这里没有 $n = 1$ 的情况，所以我们永远不会用到 $1$；类似地，对于 $> \frac{n}{2}$ 的质数，我们也永远不会用到。

那其他的数呢？仔细思考，发现一定可以全部用到。

考虑如下暴力构造：先把所有 $2$ 的幂放在开头，再抓出一个 $6$，再把 $3$ 的所有除了 $6$ 之外且未出现过的倍数接在后面，再抓出一个 $6$，再抓出一个 $10$，再把 $5$ 的所有除了 $10$ 之外且未出现过的倍数接在后面，再抓出一个 $10$……

这样构造的长度是 $O(n)$ 的（具体数值要看你怎么实现）。

算法二

本质不同点的个数的最大值是固定的，考虑最小化每个数多出现的次数之和。

现在我们先判掉 $n \leq 8$ 的情况，然后将原问题分成三部分。

• Part 1. 仅含 $[2, \sqrt{n}]$ 内的质因数的数

这部分我们可以采用一个简单的构造做到让这些数不多出现任何一次。

考虑构造 $2 \to 4 \to 8 \to \cdots \to 2k_1 \to 6 \to 3 \to 9 \to 21 \to \cdots \to 3k_2 \to 15 \to 5 \to \cdots$，即通过 $p_i p_{i + 1}$ 连接两个相邻的质数的倍数。

• Part 2. 含 $(\sqrt{n}, \frac{n}{3}]$ 内的质因数的数

这部分我们依然可以采用一个简单的构造做到让这些数不多出现任何一次。

考虑构造 $2p \to p \to 4p \to \cdots \to 3p \to 3q \to q \to 4q \to \cdots \to 2q \to \cdots$ 或 $3p \to p \to 4p \to \cdots \to 2p \to 2q \to q \to 4q \to \cdots \to 3q \to \cdots$，即通过依次交替的 $2p$ 或 $3p$ 连接两个相邻质数的倍数。

• Part 3. 含 $(\frac{n}{3}, \frac{n}{2}]$ 内的质因数的数

这部分我们还是可以采用一个简单的构造做到让所有质数 $p$ 不多出现任何一次，其对应的 $2p$ 恰好多出现一次。

考虑构造 $2p \to p \to 2p \to 2q \to q \to 2q \to \cdots$，即通过 $2p$ 连接两个相邻质数的倍数。

综上，我们可以按 $2, 3, 1$ 或 $3, 2, 1$ 的顺序使最大化本质不同点的个数为 $n - (\pi(n) - \pi(\frac{n}{2})) - 1$ 并在 $|P| = n - (\pi(n) - \pi(\frac{n}{2})) + (\pi(\frac{n}{2}) - \pi(\frac{n}{3})) - 1$ 的限制下完成构造。

算法三

观察样例四就可以发现如果我们按 $3, 2, 1$ 的顺序构造，我们还可以在 Part 3 中节省恰好一项——即 Part 3 的第一项，因为此时我们不需要首项为 $2$ 的倍数。

特判 Part 3 的第一项即可，此时我们可以在 $n \geq 10$ 时 $|P| = n - (\pi(n) - \pi(\frac{n}{2})) + (\pi(\frac{n}{2}) - \pi(\frac{n}{3})) - 2$ 的限制下完成构造。

算法四

事实上，我们还可以通过先在开头加上一个 Part. 3 中的质数并以 $2, 1, 3$ 的顺序，并节省 Part. 3 中的最后一项在 $n \geq 15$ 时 $|P| = n - (\pi(n) - \pi(\frac{n}{2})) + (\pi(\frac{n}{2}) - \pi(\frac{n}{3})) - 3$ 的限制下完成构造。

代码：

#include <stdio.h>
#include <math.h>

const int N = 1e5 + 7;
int prime[N], mpf[N], part1[N], part2[N], part3[N], vis1[N];
bool p[N], vis2[N];

inline int max(int a, int b){
	return a > b ? a : b;
}

inline int init(int n){
	int cnt = 0;
	p[0] = p[1] = true;
	mpf[1] = 0;
	for (register int i = 2; i <= n; i++){
		if (!p[i]){
			prime[++cnt] = i;
			mpf[i] = i;
		}
		for (register int j = 1; j <= cnt && i * prime[j] <= n; j++){
			int t = i * prime[j];
			p[t] = true;
			mpf[t] = max(mpf[i], prime[j]);
			if (i % prime[j] == 0) break;
		}
	}
	return cnt;
}

int main(){
	int n;
	scanf("%d", &n);
	if (n <= 3){
		printf("1\n");
		printf("1");
		return 0;
	}
	if (n == 4 || n == 5){
		printf("2\n");
		printf("2 4");
		return 0;
	}
	if (n == 6 || n == 7){
		printf("4\n");
		printf("2 4 6 3");
		return 0;
	}
	if (n == 8){
		printf("5\n");
		printf("2 4 8 6 3");
		return 0;
	}
	if (n <= 11){
		printf("8\n");
		printf("5 10 2 4 8 6 3 9");
		return 0;
	}
	int cnt = init(n), m = sqrt(n), cnt1 = 0, cnt2 = 0, cnt3 = 0, lst, i = 1;
	bool flag = false;
	for (; i <= cnt && prime[i] <= m; i++) ;
	for (; i <= cnt && prime[i] * 3 <= n; i++){
		if (!flag){
			part1[++cnt1] = prime[i] * 2;
		} else {
			part1[++cnt1] = prime[i] * 3;
		}
		for (register int j = prime[i]; j <= n; j += prime[i]){
			if (j != prime[i] * 2 && j != prime[i] * 3) part1[++cnt1] = j;
		}
		if (!flag){
			part1[++cnt1] = prime[i] * 3;
		} else {
			part1[++cnt1] = prime[i] * 2;
		}
		flag = !flag;
	}
	if (flag){
		for (register int i = 2; i <= cnt && prime[i] <= m; i++){
			int cur_nxt = prime[i + 1] > m ? 1 : i + 1, t = prime[i] * prime[cur_nxt];
			for (register int j = prime[i]; j <= n; j += prime[i]){
				if (!vis2[j] && j % 2 != 0 && j != t && mpf[j] <= m){
					part2[++cnt2] = j;
					vis2[j] = true;
				}
			}
			if (cur_nxt < cnt && t <= n && prime[cur_nxt] <= m){
				part2[++cnt2] = t;
				vis2[t] = true;
			}
		}
		for (register int i = 2; i <= n; i += 2){
			if (!vis2[i] && mpf[i] <= m){
				part2[++cnt2] = i;
				vis2[i] = true;
			}
		}
	} else {
		for (register int i = 1; i <= cnt && prime[i] <= m; i++){
			int t = prime[i + 1] <= m ? prime[i] * prime[i + 1] : prime[i] * 2;
			vis2[t] = true;
			vis1[t] = i;
		}
		for (register int i = 1; i <= cnt && prime[i] <= m; i++){
			int t = prime[i + 1] <= m ? prime[i] * prime[i + 1] : prime[i] * 2;
			for (register int j = prime[i]; j <= n; j += prime[i]){
				if (!vis2[j] && mpf[j] <= m){
					part2[++cnt2] = j;
					vis2[j] = true;
				}
			}
			if (vis1[t] == i) part2[++cnt2] = t;
		}
	}
	for (; i <= cnt && prime[i] * 2 <= n; i++){
		part3[++cnt3] = prime[i] * 2;
		part3[++cnt3] = prime[i];
		part3[++cnt3] = prime[i] * 2;
	}
	if (cnt3 == 3){
		lst = part3[cnt3];
		printf("%d\n", cnt1 + cnt2 + 2);
		printf("%d %d ", lst / 2, lst);
		for (register int i = 1; i <= cnt1; i++){
			printf("%d ", part1[i]);
		}
		for (register int i = 1; i <= cnt2; i++){
			printf("%d ", part2[i]);
		}
	} else {
		lst = part3[cnt3];
		cnt3 -= 4;
		printf("%d\n", cnt1 + cnt2 + cnt3 + 2);
		printf("%d %d ", lst / 2, lst);
		for (register int i = 1; i <= cnt1; i++){
			printf("%d ", part1[i]);
		}
		for (register int i = 1; i <= cnt2; i++){
			printf("%d ", part2[i]);
		}
		for (register int i = 1; i <= cnt3; i++){
			printf("%d ", part3[i]);
		}
	}
	return 0;
}