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

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

上期作业解析（感谢51nod提供的视频）

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

第三课  常见质数筛法

1、    直接枚举法

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

                   

2、    Sqrt（n）

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

3、    枚举质数法

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

代码如下：

程序第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）

小思考：能否将上面代码继续优化？提示：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