改进的素数筛法(线性筛)

题目内容

题目描述

输入一个正整数n,求n以内素数的个数。

输入描述

输入一个正整数n,其中n<=107。

输出描述

输出n以内素数的个数。

样例输入

6

样例输出

3

提示

介绍的筛法效率很高,但不足之处也比较明显,手动模拟一遍就会发现,很多数被处理了不止1遍,因此又造成了比较大的不必要处理。在线性筛法中,多使用一个数组保存筛选后的素数,在筛选时,如果某个合数已经被筛掉了,则break程序,保证每个合数只会被它的最小质因数筛去,因此每个数只会被标记一次,所以时间复杂度是O(n)。
提交评测
请登录后再操作

题目描述

改进的素数筛法(线性筛)
1532
0
08Level6
98
39
40%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在