3632. Establishment Of Primes

单测试点时限: 0.5 秒

内存限制: 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 numbers God first created, as the largest prime written in these ancient books was . But others found this not convincing, as it was debatable whether was a prime.

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

Find out the smallest positive integer such that there is a set (non-repeated) of positive integers where , and any prime number in can be expressed as the sum of a subset of .

输入

The input only consists of one line ().

输出

Output the smallest in the first line.

Then output positive integers separated with space, denoting . You can output the set in any order you want. The numbers should be distinct. You should not output any number larger than . (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 are . , , , .

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

5 人解决,16 已尝试。

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

9.4 EMB 奖励。

创建: 4 月,1 周前.

修改: 4 月,1 周前.

最后提交: 4 周,1 天前.

来源: EOJ Monthly 2018.8

标签