3632. Establishment Of Primes

单点时限: 0.5 sec

内存限制: 256 MB

In the beginning, there were no primes, or numbers. And God said, “let there be numbers,” and there were numbers. God thought that it might be a beautiful thing to have some of these numbers added up, and he called some of the sums “primes”.

Some scholars argued that there should be no more than $8$ numbers God first created, as the largest prime written in these ancient books was $233$. But others found this not convincing, as it was debatable whether $233$ was a prime.

If the legend somehow confuses you, here is a more formal version:

Find out the smallest positive integer $k$ such that there is a set (non-repeated) of positive integers $X$ where $|X|=k$, and any prime number in ${1,2,\ldots,n}$ can be expressed as the sum of a subset of $X$.

输入格式

The input only consists of one line $n$ ($1 \le n \le 233$).

输出格式

Output the smallest $k$ in the first line.

Then output $k$ positive integers separated with space, denoting $X$. You can output the set in any order you want. The numbers should be distinct. You should not output any number larger than $10^9$. (it doesn’t make sense anyway.)

样例

Input
2
Output
1
2
Input
5
Output
2
2 3
Input
10
Output
3
2 1 4

提示

Explanation of example 3: primes no larger than $10$ are $2, 3, 5, 7$. $2=2$, $3=1+2$, $5=1+4$, $7=1+2+4$.

Hint: The time limit is deliberately set to be very tight.

5 人解决,17 人已尝试。

6 份提交通过,共有 83 份提交。

8.6 EMB 奖励。

创建: 2 年,3 月前.

修改: 2 年,2 月前.

最后提交: 1 年,6 月前.

来源: EOJ Monthly 2018.8

题目标签