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