#P8440. [2018NOI模拟赛]质数

[2018NOI模拟赛]质数

质数(prime)

题目描述

将 1~n 分成尽可能少的集合,使得每个集合的元素和均为质数。

输入数据

一行一个正整数nn。

输出数据

第一行一个正整数 m 表示最少集合数,第二行 n 个[1,m]中的整数, 第 i 个整数表示 i 在第几个集合中。若有多种方案输出任意一种即可。

若无解输出-1。

样例输入

8

样例输出

2
1 2 2 1 1 1 1 2

数据范围

对于 30%的数据,n≤20n\le20。

对于 100%的数据,n≤6000n\le6000。