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所示。