题目描述

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼在公元前250年提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

筛选法的主要思想是​当某数是质数的时候，它的所有的倍数必然是合数，可以将它后面的倍数筛掉​。

详细列出算法如下：

任务：输入一个整数n，输出[1, n]区间的的有素数。

输入格式

一个整数n。

输出格式

第一行一个整数m，表示素数的总个数。

第二行，从小到大依次输出m个素数。

10

4
2 3 5 7

数据规模与约定

对于 100% 的测试数据，1≤n≤10^6​​。