辽宁省信息学文字公益课《跟我学NOIP》开课啦!第三课:常见质数筛法

网友投稿 2019-06-08 19:36

为了让同学们能够利用零散时间学习NOIP,辽竞委经过课程调研后,尝试采用文字版公益课进行教学。课程共分十期,聘请NOI国赛选手按照竞赛大纲归纳知识点,采用文字和视频讲解,结合练习题和题解帮助同学们快速掌握NOIP的重点和难点。由于课程都是利用业余时间编写,无法保证定期推出课程,我们尽量每周三,周末推出两期内容供大家学习,不便之处请大家谅解。文字公益课处于探索阶段,希望大家多提意见和建议,对于课程中的问题可以在留言区提问,我们会尽快进行解答。

《跟我学NOIP》面向全社会征集文字课程内容。欢迎竞赛教师,竞赛学生和社会机构踊跃投稿,共同为信息学普及和发展贡献一份力量。

上期作业解析(感谢51nod提供的视频)

建议先看完本期内容后再看习题讲解

第三课  常见质数筛法

1、    直接枚举法

枚举出2到n-1的所有数,判断x能否被整除,如果不能整除则x为质数,复杂度为O(n2)        

https://cdn.china-scratch.com/timg/190610/1936353L7-0.jpg                   

2、    Sqrt(n)

具体原理见上一次课程。复杂度O(n*sqrt(n))

https://cdn.china-scratch.com/timg/190610/1936354L8-1.jpg

3、    枚举质数法

基本思路:如果i是合数,它一定可以表示成多个质数相乘的形式,比如15=3*5,并且一定会有一个小于sqrt(i)的质数,因此,我们只需要枚举出小于sqrt(i)内所有的质数,让i和这些质数相除,如果整除则说明i是合数。

代码如下:

https://cdn.china-scratch.com/timg/190610/1936356013-2.jpg

程序第11行j<=tot&&prime[j]<=t这段代码中第一个条件判断tot变量是已经找到的质数个数,也就是质数数组prime的质数个数,因此j必须小于等于tot,否则prime[j]即为初始值0。第二个判断prime[j]<=t是因为我们只需要枚举sqrt(i)内的质数就可以了,不需要枚举到i。

4、    埃氏筛

基本思路:质数的倍数一定不是质数,所以我们可以开设一个足够大的数组,假设数组中都是质数,标记为“1”,然后枚举质数的倍数并将该数字标记成“0”,最后打印数组中标志为“1”的即为质数。

复杂度为O(nloglogn)

https://cdn.china-scratch.com/timg/190610/1936362319-3.jpg

小思考:能否将上面代码继续优化?提示:6=2*3,2的倍数有6,3的倍数也有6,相当于6被标记了两次,是否可以只标记一次?

巩固练习:

请你帮小瓜将正整数n分解质因数,并从小到大输出所有的质因数(如果一个质因数出现多次,则输出多次)。

输入:

一行一个正整数n,保证1<=n<=10^8。

输出:

若干行,每行表示n的一个质因数。按从小到大的顺序输出质因数。

输入样例:

12

输出样例:

2

2

3

作业提交评测请登录:

http://class.51nod.com/Course/Problem.html#!#courseProblemId=388&classId=22

作业解析:

将在下次”跟我学NOIP”给出题解,敬请关注!

往期链接:

辽宁省信息学文字公益课《跟我学NOIP》开课啦!第一课:快速幂

辽宁省信息学文字公益课  《跟我学NOIP》开课啦!第二课:质数和约数

公益课发起人

--end--

声明:本文章由网友投稿作为教育分享用途,如有侵权原作者可通过邮件及时和我们联系删除:freemanzk@qq.com