埃氏筛点亮表

题目描述

使用埃拉托斯特尼筛法找出闭区间 [2,N] 中的所有质数，输出质数数量和完整名单。

输入格式

一行输入整数 N，满足 2≤N≤1000000。

输出格式

第一行输出不超过 N 的质数数量。第二行按从小到大的顺序输出全部质数，相邻两个数之间用一个空格分隔。

样例

输入

2

输出

1
2