CF45G

考虑哥德巴赫猜想：一个偶数可以被拆分两个质数。

所以我们考虑如果不是偶数的话，我们拆分成\((2,m-2)\)或者\((3,del(m - 3))\)

如果是偶数的话\(del(m)\)，我们直接枚举其中一个质数。

// Problem: CF45G Prime Problem

// Contest: Luogu

// URL: https://www.luogu.com.cn/problem/CF45G

// Memory Limit: 250 MB

// Time Limit: 1000 ms

//

// Powered by CP Editor (https://cpeditor.org)

#include<iostream>

#include<cstdio>

#define ll long long

#define N 6005

ll ans[N];

ll n;

inline bool check(ll x){

	if(x <= 1)return 0;

	for(int i = 2;i <= x / 2;++i)

	if(!(x % i))return 0;

	return 1;

}

int main(){

	scanf("%lld",&n);

	ll m = n * (n + 1) / 2;

	if(m % 2 == 1){

		if(check(m - 2)){

			ans[2] = 2;

		}else{

			ans[3] = 3;

			m -= 3;

		}

	}

	if(m % 2 == 0){

		for(int i = 2;i <= n;++i)

		if(check(i) && check(m - i) && !ans[i]){

			ans[i] = 2;

			break;

		}

	}

	for(int i = 1;i <= n;++i)

	std::cout<<((!ans[i]) ? 1 : ans[i])<<" ";

}