GESP等级考试C++5级20-素数判断法3

2.3 线性筛埃氏筛里一个合数会被划多次（如 30 会被 2、3、5 各划一次），做了冗余工作。线性筛的核心目标：每个合数只被它的最小质因子划掉，且只划一次，从而做到严格 O(n)。线性筛的原理：维护一个已找到的素数数组prime[]，对每个 i：（1）若 i 没被标记过，说明 i 是素数，加入素数表；（2）用 i 去乘素数表里的每个素数 p，把i * p划掉；（3）i能被p整除（即i % p == 0）时立刻 break。线性筛的代码如图5所示。