第三课：常见质数筛法

　　为了让同学们能够利用零散时间学习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<=totprime[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输出样例：223

少儿编程培训哪家好第三课：常见质数筛法