2.3 線性篩埃氏篩里一個合數(shù)會被劃多次（如 30 會被 2、3、5 各劃一次），做了冗余工作。線性篩的核心目標：每個合數(shù)只被它的最小質(zhì)因子劃掉，且只劃一次，從而做到嚴格 O(n)。線性篩的原理：維護一個已找到的素數(shù)數(shù)組prime[]，對每個 i：（1）若 i 沒被標記過，說明 i 是素數(shù)，加入素數(shù)表；（2）用 i 去乘素數(shù)表里的每個素數(shù) p，把i * p劃掉；（3）i能被p整除（即i % p == 0）時立刻 break。線性篩的代碼如圖5所示。