素数筛法

优化版埃氏筛法（NlogN）

• 优化后的筛法可以减少大量的重复筛，但是仍然无法做到所有数只筛一次。
  $例如：3*35=7*15=105，\\ i=3时，\\ j=3*3\\ j=3*3+3*2 \\ j=3*3+3*2+3*2=3*3+3*4\\ .......\\ j=3*3+3*32=3*35\\ \\ ------------------\\ 当i=7时\\ j=7*7\\ j=7*7+7*2\\ ............\\ j=7*7+7*8=7*15\\ 此处重复筛了105这个数$例如：3∗35=7∗15=105，i=3时，j=3∗3j=3∗3+3∗2j=3∗3+3∗2+3∗2=3∗3+3∗4.......j=3∗3+3∗32=3∗35−−−−−−−−−−−−−−−−−−当i=7时j=7∗7j=7∗7+7∗2............j=7∗7+7∗8=7∗15此处重复筛了105这个数

bool primer[N];//[0,N],合数值为1，素数为0,素数定义为大于1的自然数中
void find_primer(int N){
    int sqr=sqrt(N);
    
    for(int i=4;i<N;i+=2)primer[i]=1;//2的倍数标记为合数

    for(int i=2;i<=sqr;i++){
        if(!primer[i])
            for(int j=i*i;i<=N;j+=i*2)//j从i*i开始，i*(k)（k=2,3,,,,(i-1)）已经被(k)筛过了,
                primer[j]=1;           //i(素数)和j都为奇数，j+i为偶数，故为j+2i;
    }
}

欧拉筛法（O(N) 最小质因子的应用）

bool vis[N];//标记非素数，
int primer[N];//存素数
int cnt=0;//记录素数个数，
void find_primer(int N){
    for(int i=2;i<=N;i++){
        if(!vis[i])primer[cnt++]=i;
        
        for(int j=0;j<cnt&&primer[j]*i<=N;j++){
            vis[i*primer[j]]==1;//筛

            if(i%primer[j]==0)break;//关键！！！找到i*primer[j]的最小质因子primer[j]，退出
        }
    }
}

• 任何合数都能表示成素数之积，也即每个合数都有一个最小质因子，每个合数都被其最小质因子筛去过一次，故为线性时间

• $当i \% primer[j]==0时，i=k*primer[j]【k \ge primer[j],因为primer[j]是第一个满足整除关系的素数,所以另一个因数k\geq primer[j]】primer[j]为i*primer[j]【k*primer[j]*primer[j]】的最小质因子，,若继续筛下去，下一个数为i*primer[j+1]=k*primer[j]*primer[j+1]必然会被后面的数重新筛去$当i%primer[j]==0时，i=k∗primer[j]【k≥primer[j],因为primer[j]是第一个满足整除关系的素数,所以另一个因数k≥primer[j]】primer[j]为i∗primer[j]【k∗primer[j]∗primer[j]】的最小质因子，,若继续筛下去，下一个数为i∗primer[j+1]=k∗primer[j]∗primer[j+1]必然会被后面的数重新筛去

欧拉筛法打表观察：

for (int i = 2;i <= maxn; i++) {
    cout<<" i = "<<i<<endl;
    if (!visit[i]) 
        prime[++prime[0]] = i;      //纪录素数， 这个prime[0] 相当于 cnt，用来计数
    
    for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {        
        cout<<"  j = "<<j<<" prime["<<j<<"]"<<" = "<<prime[j]<<" i*prime[j] = "<<i*prime[j]<<endl;
        
        visit[i*prime[j]] = 1;
        
        if (i % prime[j] == 0) break;
    }
}

i = 8 ，j = 1，prime[j] = 2，如果不跳出循环，prime[j+1] = 3，83 = 243 = 212，在i = 12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。