做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 1196. -- 筛选法求素数

1196: 筛选法求素数

时间限制: 1 Sec  内存限制: 0 MB
提交: 488  解决: 236
[上一题][提交][讨论版][状态][下一题]

题目描述

筛选法求素数是一种高效求素数的方法,其具体算法如下:
从2开始把连续的整数放入筛中,首先确定筛中第一个数2是素数。并从筛中晒去所有2的倍数(不包括2);然后从2以后开始查找,找到筛中剩下的第一个数,它也是素数,并从筛中筛去它的所有倍数(不包括本身)。如此反复执行,直到无数可筛为止。这时筛中剩下的就是这一串就是素数。
提示:
可以用一个数组ss作为筛,数组的下标代表连续的整数,若储存的是0时,代表不在筛中,储存的是1时,代表在筛中。如ss[2]=1代表整数2在筛中。
 
本题中要求输入一个数n,输出2到n中的所有素数。

输入

一行n(300000>n)

输出

2到n的所有素数

样例输入

12

样例输出

2 3 5 7 11 

标签

[上一题][提交][讨论版][状态][下一题]