欧拉线性素数筛(转)

简介

在埃氏筛中,我们会重复筛到同一个数,例如12同时被2和3筛到,15同时被3和5筛到。所以我们引入欧拉筛,也叫线性筛,可以在$O(n)$的时间内完成对2~n的筛选。它的核心思想是:让每一个最小的合数被其最小质因数筛到


埃式素数筛

原理

这是最简单的素数筛,一次性打表,效率不是很高,但是比直接判断素数效率高得多。反正开O2冲就完事了。


Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×