批量求素数

提交数: 1208, 通过率: 38.41%, 平均分: 63.51

题目描述:

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

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

详细列出算法如下：

1592704261835154119.png

1592704665872214679.png

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

输入格式:

一个整数n。

输出格式:

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

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

样例输入:

10

样例输出:

4
2 3 5 7

提示:

对于 100% 的测试数据，1≤n≤106 ​​。

筛选素数还有一种更快的算法：欧拉的线性筛法，请有兴趣的同学自己去学习。

时间限制: 1000ms
空间限制: 256MB

来源: 原创