线性筛素数（欧拉筛）

欧拉筛为啥是\(O(n)\)的呢？我们先来看看代码。

#include 
    
     using namespace std;const int maxn=10000000;int n, m, prime[maxn], isnt_prime[maxn], tot;void get_prime(int n){    isnt_prime[0]=isnt_prime[1]=1;    for (int i=2; i<=n; ++i){  //当前数是所有数小于n的数而不只是素数，这是欧拉筛与埃氏筛的区别        if (!isnt_prime[i]) prime[++tot]=i;        for (int j=1; j<=tot&&i*prime[j]<=n; ++j){  //当前数乘上的素数为prime[j]            isnt_prime[i*prime[j]]=1;            if (i%prime[j]==0) break;        }    }}int main(){    scanf("%d%d", &n, &m);    get_prime(n);    int t;    for (int i=0; i
    

设当前数i的分解为\(i=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}\ (p_1<p_2<...<p_k)\)，当前枚举的i要乘上的素数为\(p_j\)，那么，我们要筛掉的数就是\(i*p_j\)。

if (i%prime[j]==0) break;

这一行很重要。欧拉筛的特点，在于每个合数都被它的最小质因数筛掉。假设，当前被筛的数为\(x=i*p_j\)。如果\(p_j>p_1\)，意味着\(p_j\)并不是x的最小质因数，等到i变的更大，变成某个\(i'\)，x是可以被\(i'*p_1\)筛掉的。因此，如果发现\(p_j>p_1\)，就没有必要再继续枚举p下去了。代码的含义其实相同：如果\(p_j\mid i\)，意味着\(p_j=p_1\)，因此后面枚举的\(p_j\)都大于等于\(p_1\)，就不用继续枚举p了。