素数筛

Star_LIcsAy · 2021-10-01 17:17:32 · 个人记录

- \mathcal{Eratosthenes}筛法

核心思想：在找到一个质数 p 的时候，将 p 在范围内的倍数都标记一遍。以这种方式，下一个未被标记的数就是下一个质数。

时间复杂度：O(N\ \log\ \log\ N) 很接近线性了，然而并不是。

void get(int x){
    for(int i=2;i<=x;i++){
        if(!st[i]){
            p[++k]=i;
            for(int j=2;j*i<=x;j++)
                st[j*i]=true;
        }
    }
}

线性筛法

核心思想：将每个合数以它最小的质因数来标记，确保每个合数只会被标记一遍。

时间复杂度：O(N)

void get(int x){
    for(int i=2;i<=x;i++){
        if(!st[i])
            p[++k]=i;
        for(int j=1;j<=k && p[j]*i<=x;j++){
            st[p[j]*i]=true;
            if(!i%p[j]) break;
        }
    }
}

例题：P3383 【模板】线性筛素数

#include<bits/stdc++.h>
using namespace std;

const int N=1e8+20;

int p[N>>2],k=0;
bool st[N];

void get(int x){
    for(int i=2;i<=x;i++){
        if(!st[i])
            p[++k]=i;
        for(int j=1;j<=k && p[j]*i<=x;j++){
            st[p[j]*i]=true;
            if(!i%p[j]) break;
        }
    }
}

int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    get(n);
    for(int i=1;i<=q;i++){
        int x;
        scanf("%d",&x);
        printf("%d\n",p[x]);
    }
    return 0;
}