欧拉筛（线性筛）——算法笔记

欧拉筛是一种筛选素数算法，也叫线性筛，因为他的时间复杂度很优秀，能做到o（1），而一般的暴力判断方法要到o（n）。

作为一种基础算法，代码不长，但是其中蕴含着一种很精妙的数学思想，即素数的整数倍一定不是素数。

要保证时间严格线性，我们还应当在筛选的时候注意重复筛选的次数，做到不重不漏，这里又有一个巧妙的判断方式：只判断这个数的最小质因数，这样就能达到一个数只判一次。

#include<iostream> using namespace std; int a[100]={1,1}; int b[100]={0}; int main(){ int n; cin>>n; int cnt=0; for(int i=2;i<=n;i++){ if(!a[i]) { b[++cnt]=i; for(int j=2;j<=cnt;j++){ if(j*b[i]>n) break; a[j*b[i]]=1; if(i%b[j]==0) break; } } } }

懒得加注释了，只是自己的笔记，csdn上有更多讲得很好的文章，可以多看看。