---
title: "筛素数"
created: 2025-11-28
tags:
  - 算法
---

# 筛素数

## 题目 [筛质数](https://www.acwing.com/solution/content/7950/)

![[image-ab1c8045.png]]

## 思路分析

如果要找一段区间里 质数的个数

首先最容易想到的办法就是 对每个数判断一下是不是素数 是的话 cnt++

还是那句话 填空题用 编程题别想

tle

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

bool is_prime(int x){
    if(x<2) return false;
    for(int i=2;i<=x/i;i++)
        if(x%i==0)
            return false;
    return true;
}

int main(){
    int n;cin>>n;
    int cnt=0;
    for(int i=2;i<=n;i++)
        if(is_prime(i))
            cnt++;
    cout<<cnt;
    return 0;
}
```

然后这里解释三种筛法

首先朴素的就是

从2——n 把所有的倍数全都标记掉不是素数 （能是2的倍数 反过来不就是除1和它本身外还可以有个2\*x 肯定不是素数）

若某个数没被标记成非素数 就把它记录下来

这样就可以在$O(nlog\_n)$内筛选出n内所有的素数

怎么表示某数的所有倍数 用到乘法原理本质是加法 2+2+2 三个2相加等于2\*3

那么就可以用累加的方式 表示每次乘多一个`for(int j=i;j≤n;j+=i)`

167ms

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

const int N=1000010;
int primes[N];
bool st[N];
int cnt=0;
int n;

void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i])
            primes[cnt++]=i;//把素数存起来
        for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
            st[j]=true;
        }
    }
}

int main(){
    cin>>n;
    get_primes();
    cout<<cnt;
    return 0;
}
```

其实只需要把素数的倍数筛掉即可

合数的倍数会重复做很多无用功 比如2的倍数全筛了 4的倍数又来全筛 发现都已经被筛过了

这叫做 埃氏筛法 $O(nloglog\_n)$

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1000010;

int primes[N];

bool st[N];

int cnt=0;

int n;

void get_primes(){

    for(int i=2;i<=n;i++){

        if(!st[i]){ //可以用质数就把所有的合数都筛掉;

            primes[cnt++]=i;

            for(int j=i;j<=n;j+=i)

                st[j]=true;

        }

    }

}

int main(){

    cin>>n;

    get_primes();

    cout<<cnt;

    return 0;

}
```

还有一种线性筛 但是我感觉前面已经够用了 听一下思路得了

意思是说 每个被筛的数 范围再次缩小 从所有数去筛倍数 变成所有质数去筛倍数 再变成 最小质因子去筛倍数

34ms

```cpp
void get_primes(){

    for(int i=2;i<=n;i++){

        if(!st[i])

            primes[cnt++]=i;

        for(int j=0;primes[j]<=n/i;j++){//primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就没啥意义了

            st[primes[j]*i]=true;//用最小质因子去筛合数

            //1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子

            //那么只可能是此时的primes[j]<i的最小质因子,所以primes[j]*i的最小质因子就是primes[j];

            //2)当有i%primes[j]==0时,说明i的最小质因子是primes[j]

            //因此primes[j]*i的最小质因子也就应该是prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，

            //就不是用最小质因子去更新了,因为i有最小质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该

            //退出循环，避免之后重复进行筛选。

            if(i%primes[j]==0)

                break;

        }

    }

}

//完整代码

#include<bits/stdc++.h>

using namespace std;

const int N=1000010;

int primes[N];

bool st[N];

int cnt=0;

int n;

void get_primes(){

    for(int i=2;i<=n;i++){

        if(!st[i])

            primes[cnt++]=i;

        for(int j=0;primes[j]<=n/i;j++){

            st[primes[j]*i]=true;

            if(i%primes[j]==0)

                break;

        }

    }

}

int main(){

    cin>>n;

    get_primes();

    cout<<cnt;

    return 0;

}
```

思路不难 但是很多细节要搞懂就比较麻烦

若n在10的6次方的话,线性筛和埃氏筛的时间效率差不多,若n在10的7次方的话,线性筛会比埃氏筛快了大概一倍.

后面再说吧 先把线性筛放了 掌握埃氏筛就行了

## 代码实现

```

```

## 同类题型

## 视频讲解

---
⬅️ [[夏洛克和他的女朋友|夏洛克和他的女朋友]] 🏠 [[00-刷题理模型]] ➡️ [[质数距离|质数距离]]