质数筛选法埃氏筛学习目标理解什么是质数理解筛选法的基本思想能看懂筛选法的代码能手动模拟筛选过程能独立写出求 2 到 n 之间所有质数的程序一、什么是质数质数是指大于 1 的自然数中除了 1 和它本身以外不能被其他自然数整除的数。数是不是质数原因2是只能被 1 和 2 整除4不是能被 2 整除7是只能被 1 和 7 整除9不是能被 3 整除1不是1 不是质数常见的质数2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ...二、为什么要用筛选法如果我们要找出 2 到 n 之间的所有质数可以一个一个判断。但这样效率比较低。筛选法的思路更简单不一个一个判断而是先把所有数默认成质数然后不断把“不是质数”的数筛掉。就像从一堆数字中把合数一个个划掉最后剩下的就是质数。三、筛选法的基本思想筛选法可以分成四步把 2 到 n 的所有数默认标记为质数。从 2 开始如果这个数还没有被筛掉说明它是质数。把这个质数的所有倍数都筛掉。继续往后找直到筛完为止。最后没有被筛掉的数就是质数。四、手动模拟筛出 2 到 20 的质数初始时2 到 20 都默认是质数2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20第一步筛 2 的倍数2 是质数所以把 2 的倍数筛掉4, 6, 8, 10, 12, 14, 16, 18, 20筛完后2 3 × 5 × 7 × 9 × 11 × 13 × 15 × 17 × 19 ×第二步筛 3 的倍数3 没有被筛掉所以 3 是质数。把 3 的倍数筛掉9, 15注意6、12、18 已经被 2 筛掉了。筛完后2 3 × 5 × 7 × × × 11 × 13 × × × 17 × 19 ×第三步看 55 没有被筛掉所以 5 是质数。但5 * 5 2525 已经大于 20所以不需要继续筛。第四步得到结果最后没有被筛掉的数是2, 3, 5, 7, 11, 13, 17, 19这些就是 2 到 20 之间的质数。五、用数组表示“打叉”程序里不能真的画叉所以用数组记录状态。可以这样设计a[i]1;// 表示 i 暂时是质数a[i]0;// 表示 i 被筛掉了不是质数对应关系如下生活动作程序表示默认是质数a[i] 1给某个数打叉a[j] 0判断是否质数if(a[i] 1)六、完整代码#includeiostreamusingnamespacestd;inta[1005]{0};intmain(){intn;cinn;// 第一步默认 2 到 n 都是质数for(inti2;in;i){a[i]1;}// 第二步开始筛选for(inti2;i*in;i){if(a[i]1){for(intji*i;jn;ji){a[j]0;}}}// 第三步输出质数for(inti2;in;i){if(a[i]1){coutiendl;}}return0;}七、代码逐段讲解1. 初始化数组for(inti2;in;i){a[i]1;}意思是先把 2 到 n 都假设成质数。2. 开始筛选for(inti2;i*in;i){if(a[i]1){for(intji*i;jn;ji){a[j]0;}}}这段代码的意思是从 2 开始检查每个数。如果a[i] 1说明 i 还没有被筛掉所以 i 是质数。然后把 i 的倍数都标记成 0。j i表示每次加一个 i也就是枚举 i 的倍数。例如当i 2时j 4, 6, 8, 10, 12 ...当i 3时j 9, 12, 15, 18 ...八、重点难点一为什么从i * i开始代码中有这一句for(intji*i;jn;ji)问为什么不是从2 * i开始原因是比i * i小的倍数已经被更小的质数筛掉了。例如筛到 5 时5 * 2 10 5 * 3 15 5 * 4 20这些数其实早就被筛过了数被谁筛掉10被 2 筛掉15被 3 筛掉20被 2 筛掉所以 5 真正需要筛的第一个新倍数是5 * 5 25因此可以从i * i开始。九、重点难点二为什么外层循环是i * i n代码中有这一句for(inti2;i*in;i)意思是只需要筛到 n 的平方根附近就够了。原因是如果一个数不是质数它一定有一个不超过它平方根的因数。理解这句话的关键在于“因数成对出现且必然一个≤√n、一个≥√n”。如果一个数不是质数它一定能分解为两个大于1的因数而这两个因数不可能同时大于√n因此其中较小的那个一定不超过√n。核心逻辑因数成对出现任何合数nnn都可以写成两个大于1的整数之积na×bn a \times bna×b。关键在于aaa和bbb不可能同时大于n\sqrt{n}n​。用反证法证明假设ana \sqrt{n}an​且bnb \sqrt{n}bn​那么a×bn×nna \times b \sqrt{n} \times \sqrt{n} na×bn​×n​n这与a×bna \times b na×bn矛盾所以aaa和bbb中至少有一个 ≤n\sqrt{n}n​。直观例子以n36n 36n36为例366\sqrt{36} 636​6列出所有因数对因数对较小的因数是否 ≤ 62 × 182✅3 × 123✅4 × 94✅6 × 66✅可以看到每一对中较小的那个都不超过6。实际意义这个性质是试除法判断质数的理论基础。判断一个数nnn是否为质数时不需要从2一直试到n−1n-1n−1只需要试到⌊n⌋\lfloor\sqrt{n}\rfloor⌊n​⌋就够了。如果到n\sqrt{n}n​都没找到因数那它一定是质数。例如判断n97n 97n97是否为质数只需试到⌊97⌋9\lfloor\sqrt{97}\rfloor 9⌊97​⌋9即检查2、3、4、5、6、7、8、9能否整除97。都不能所以97是质数。例如判断 4949 7 * 7只要筛到 7就能把 49 筛掉。如果某个数有更大的因数那它一定也有一个更小的因数早就被筛掉了。所以外层循环不需要一直跑到 n。十、输出结果for(inti2;in;i){if(a[i]1){coutiendl;}}意思是最后再检查一遍如果a[i]还是 1说明它没有被筛掉所以它是质数。十一、程序流程总结整个程序可以概括成五步输入 n。把 2 到 n 都标记成质数。从 2 开始找到还没被筛掉的数。把这个数的倍数全部筛掉。最后输出所有没有被筛掉的数。十二、记忆口诀先假设都是质数。从 2 开始找。找到质数就把它后面的倍数筛掉。筛到平方根就够了。最后没被筛掉的就是质数。十三、课堂练习练习 1手动模拟请用筛选法找出 2 到 30 之间的所有质数。要求先写出 2 到 30。依次筛掉 2、3、5 的倍数。写出最后剩下的质数。参考答案2, 3, 5, 7, 11, 13, 17, 19, 23, 29练习 2代码填空补全下面代码#includeiostreamusingnamespacestd;inta[1005]{0};intmain(){intn;cinn;for(inti2;in;i){a[i]____;}for(inti2;i*in;i){if(a[i]1){for(intj____;jn;j____){a[j]____;}}}for(inti2;in;i){if(a[i]____){coutiendl;}}return0;}参考答案a[i]1;ji*i;ji;a[j]0;a[i]1;练习 3思考题为什么 1 不是质数为什么筛选法从 2 开始而不是从 1 开始如果n 10外层循环会检查哪些 i为什么j i可以枚举 i 的倍数十四、常见错误提醒错误 1从 1 开始筛选错误写法for(inti1;i*in;i)原因1 不是质数而且 1 的倍数是所有数会把所有数都筛掉。正确写法for(inti2;i*in;i)错误 2忘记判断a[i] 1错误写法for(inti2;i*in;i){for(intji*i;jn;ji){a[j]0;}}问题即使 i 已经被筛掉也会继续筛它的倍数虽然结果可能正确但效率低逻辑不清晰。正确写法if(a[i]1){for(intji*i;jn;ji){a[j]0;}}错误 3数组开得太小如果 n 可能到 1000数组至少要开inta[1005];否则可能会越界。十五、课堂总结筛选法的核心思想是不直接判断每个数是不是质数而是把所有合数提前筛掉。程序实现的关键是用数组记录每个数是否被筛掉。从 2 开始找质数。把质数的倍数全部标记成合数。外层循环只需要到i * i n。内层循环可以从i * i开始。