跟出题人题解感觉不是很一样，思维量似乎小一点。

直接说解法：要构造 的答案，就找到一个素数 ，其中 ，于是 区间都可以构造出来， 。这样操作后，问题就剩下构造 的答案。

可行性：要找到符合条件的素数 ，就要求对于任意正整数 ， 区间里存在素数。想一下 比较小的情况都符合， 比较大的情况不符合倒是会很奇怪，打表也可以发现题目中的数据范围可以保证可行。

#include<bits/stdc++.h>
using namespace std;

int ans[1000005];
bool isPrime(int x) {
	for(int i = 2; i * i <= x; i++) if(x % i == 0) return 0;
	return 1;
}
void solve(int n) {
	if(n == 0) return;
	for(int i = 1; i <= n; i++) {
		if(isPrime(n + i)) {
			for(int j = i; j <= n; j++)
            	ans[j] = n + i - j;
			solve(i - 1);
			return;
		}
	}
}

int main() {
	int n;
	cin >> n;
	solve(n);
	for(int i = 1; i <= n; i++)
    	printf("%d ", ans[i]);
	return 0;
}