← 返回题目列表

Codeforces · 576/A

A. Vasya 和 Petya 的游戏

中文机器翻译题面 查看原题

Vasya 和 Petya 正在玩一个简单的游戏。 Vasya 想到了 1 到 n 之间的数字 x,Petya 尝试猜测这个数字。

Petya 可以提出这样的问题:“未知数能被数字 y 整除吗?”。

游戏按照以下规则进行:首先 Petya 提出所有他感兴趣的问题(也可以不问任何问题),然后 Vasya 对每个问题回答“是”或“否”。收到所有答案后,Petya 应该确定 Vasya 想到的数字。

不幸的是,Petya 不熟悉数论。帮助他找到他应该问的最少问题数,以保证猜测出 Vasya 的数字,以及他应该问的问题的数字。

输入

单行包含数字 n (1 ≤ n ≤ 103)。

输出

打印问题序列 k (0 ≤ k ≤ n) 的长度,后跟 k 个数字 — 问题 yi (1 ≤ yi ≤ n)。

如果存在多个最小长度的正确问题序列,则允许打印其中任何一个。

示例

输入 #1

4

输出 #1

3
2 4 3

输入 #2

6

输出 #2

4
2 4 3 5

注意

从答案到第一个样本测试的顺序实际上是正确的。

如果未知数不能被序列号之一整除,则它等于 1。

如果未知数能被 4 整除,则为 4。

如果未知数能被 3 整除,则未知数为 3。

否则,它等于2。因此,问题的顺序可以让你猜测未知数。可以证明,不存在长度为 2 或更短的正确问题序列。