前言

素数筛，即把一定范围内的素数筛选出来，是ACM竞赛中的一项基本技能，一般来说他不会单独形成题目出现，但是它却是许多题目或者算法的基础步骤，因此掌握素数筛对我们解决信息竞赛问题有很大帮助。

预备知识

1. 素数：如果一个数除了1和它本身之外，不能被任何数字整除，则此数为素数，否则为合数（约定0,1既不是素数也不是合数）
2. 算术基本定理：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积
3. 数学推论：若一个数可以进行因数分解，则得到的两个因数一定是有一个大于等于$\sqrt{x}$，另一个小于等于$\sqrt{x}$.

判断素数

在讲解如何筛素数前，首先讲一下如何判断一个数字是否为素数。在现代数学上，存在的素数公式大多都属于筛法公式，即通过素数筛来推导的公式。但是想要快速判断一个数是否为素数，或者第n个素数是多少，暂时没有普适的计算公式。在算法竞赛中，我们通常使用试除法来判断一个数是否是素数，代码如下：

bool judge(int n)
{
    if(n < 2) return false; 
    for(int i = 2; i*i <= n; ++i) {
        if(n%i == 0) return false;
    }
    return true;
} 

根据预备知识中的数学推论可知，我们其实没有必要枚举到n，只需枚举到$\sqrt{x}$即可，代码中使用 i*i <= n 而不是使用sqrt()，主要是因为浮点运算比整数运算慢。（在之前带信息集训的时候，那些学生也尝试在这上面继续优化，跳过了所有偶数的判断，也是一种优化方法）

一、朴素筛法

时间复杂度：$O(n\sqrt{n})$
算法介绍：朴素筛法是基于上文的判断素数的方法推演出来的，即把每个数都判断一遍是否为素数，此算法虽然简单，但复杂度高

const int maxn = 1e7; // 筛选范围 

int cnt = 0; // 记录素数个数
int prime[maxn], isprime[maxn]; // 记录素数，标记素数

bool judge(int n)
{
    if(n < 2) return false; 
    for(int i = 2; i*i <= n; ++i) {
        if(n%i == 0) return false;
    }
    return true;
} 

void init()
{
    isprime[0] = isprime[1] = 0; // 0和1不是素数 
    for(int i = 2; i < maxn; ++i) {
        if(judge(i)) {
            isprime[i] = 1;
            prime[++cnt] = i;
        }
    }
}

二、埃氏筛法

时间复杂度：$O(nloglogn)$
算法介绍：埃拉托斯特尼筛法，利用当前已经找到的素数，从后面的数中筛去当前素数的倍数，由预备知识2可知，当前素数已经是筛去数的质因子，如此下去能筛除所有之后的合数，是一种比较快的筛法，缺点是合数可能会被重复筛去

const int maxn = 1e7; // 筛选范围 

int cnt = 0; // 记录素数个数
int prime[maxn], isprime[maxn]; // 记录素数，标记素数

void init()
{
    memset(isprime, 1, sizeof(isprime)); // 记得初始化
    isprime[0] = isprime[1] = 0; // 0和1不是素数
    for(int i = 2; i < maxn; ++i) {
        if(isprime[i]) {
            prime[++cnt] = i;
            // 筛去素数的倍数,美中不足是会筛除多次,比如15，同时被3和5筛去
            for(int j = 2; j*i < maxn; ++j) {
                isprime[i*j] = 0;
            }
        }
    } 
}

三、欧拉筛法

时间复杂度：$O(n)$
算法介绍：因为埃氏筛法会重复筛到同一个数，所以后来就研究出了欧拉筛，也叫线性筛，欧拉筛法只筛除一次，它的核心思想是：让每一个合数被其最小素因数筛到。（prime数组可以从数组0下标或者1下标开始记录素数，下面给出两种写法）

const int maxn = 1e7; // 筛选范围最大

int cnt = 0; // 记录素数个数
int prime[maxn]; // 记录素数
int factor[maxn];// 记录最小素因子 
// prime数组下标从1开始记录的写法，里面的maxn可看情况换成输入的范围n
void init()
{
    for(int i = 2; i < maxn; ++i) {
        if(!factor[i]) { // 没找到素因子，那就是素数 
            prime[++cnt] = i;
            factor[i] = i;
        } 
        for(int j = 1; j<=cnt && prime[j]*i < maxn ; ++j) {
            factor[prime[j]*i] = prime[j];
            if(!(i%prime[j])) break; // 筛的数已经被前面的数筛过 
        }
    } 
}
// prime数组下标从0开始记录的写法，里面的maxn可看情况换成输入的范围n
void init2()
{
    for(int i = 2; i < maxn; ++i) {
        if(!factor[i]) { // 没找到素因子，那就是素数 
            prime[cnt++] = i;
            factor[i] = i;
        } 
        for(int j = 0; j<cnt && prime[j]*i < maxn ; ++j) {
            factor[prime[j]*i] = prime[j];
            if(!(i%prime[j])) break; // 筛的数已经被前面的数筛过 
        }
    } 
}

int prime[maxn];
int vis[maxn];
void Prime(){
    memset(vis, 0, sizeof(vis));
    memset(prime, 0, sizeof(prime));
    for (int i = 2;i <= maxn; i++) {
        cout<<" i = "<<i<<endl;
        if (!vis[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;
            vis[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

洛谷P3383 【模板】线性筛素数
题意： 给定一个范围 n，有 q 个询问，每次输出第 k 小的素数
数据范围： $对于100%的数据，n=10^8，1<=q<=10^6，保证查询的素数不大于 n $
思路： 数据范围 n 比较大，每次查询都找一遍素数肯定会超时，因此在一开始就直接把素数筛出来，然后每次查询去找prime数组就好

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e8+5; // 筛选范围 

int cnt = 0; // 记录素数个数
int prime[maxn]; // 记录素数
int factor[maxn];// 记录最小素因子 

int n,q,k;

void init()
{
    for(int i = 2; i < n; ++i) {
        if(!factor[i]) { // 没找到素因子，那就是素数 
            prime[++cnt] = i;
            factor[i] = i;
        } 
        for(int j = 1; j<=cnt && prime[j]*i < n ; ++j) {
            factor[prime[j]*i] = prime[j];
            if(!(i%prime[j])) break; // 筛的数已经被前面的数筛过 
        }
    } 
}

int main()
{
    scanf("%d%d", &n, &q);
    init();
    while(q--)
    {
        scanf("%d", &k);
        printf("%d\n", prime[k]);
    }
    return 0;
}

四、区间筛法

介绍：区间筛法并不是一种算法，而是一种思路，一般用于解决大区间素数个数的问题，对于超大区间，数组是开不到这么大的，所以要用偏移来筛选。
例子：给定整数a和b，请问区间[a,b)内有多少个素数？a<b<=$10^{12}$,b-a<=$10^6$
思路：可知b以内合数的最小素因数一定不超过$\sqrt{b}$，如果有$\sqrt{b}$以内的素数表的话，就可以把筛选法用在[a,b)上了,先分别做好$[2,\sqrt{b})$的表和[a,b)的表，然后从$[2,\sqrt{b})$的表中筛得素数的同时，也将其倍数从[a,b)的表中划去，最后剩下的就是区间[a,b)内的素数了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000005;

bool is_prime[maxn];
bool is_prime_small[maxn];
ll prime[maxn];
ll prime_num=0;

//对区间[a,b)内的整数执行筛法，is_prime[i-a]=true  ---  表示i是素数 注意这里下标偏移了a，所以从0开始。
void segment_sieve(ll a,ll b) {
    for(ll i=0;i*i<b;++i) is_prime_small[i]=true; //对[2,sqrt(b))的初始化全为质数
    for(ll i=0;i<b-a;++i) is_prime[i]=true; //对下标偏移后的[a,b)进行初始化

    for(ll i=2;i*i<b;++i) {
        if(is_prime_small[i]) {
            for(ll j=2*i;j*j<b;j+=i) is_prime_small[j]=false;  //筛选[2,sqrt(b));
            //(a+i-1)/i得到最接近a的i的倍数，最低是i的2倍，然后筛选
            for(ll j=max(2LL,(a+i-1)/i)*i;j<b;j+=i) is_prime[j-a]=false;
        }
    }
    for(ll i=0;i<b-a;++i)  //统计个数
        if(is_prime[i]) prime[prime_num++]=i+a;
}

int main()
{
    ll a,b;
    while(~scanf("%lld%lld",&a,&b))
    {
        prime_num=0;
        memset(prime,0,sizeof(prime));
        segment_sieve(a,b);
        printf("%lld\n",prime_num);
    }
    return 0;
}

参考资料

• 算法学习笔记: 素数筛
• 求素数为什么只需要求到平方根就行？
• 四种素数筛法
• 区间素数筛法
• ACM算法——线性筛
• 欧拉筛法（线性筛）的学习理解

版权属于：PCsky

本文链接：http://www.hyouka.club/index.php/archives/140/

转载时须注明出处及本声明