【总结】素数筛方法详解前言一、素数的判定二、埃氏筛法三、欧拉筛法四、例题

98 阅读 0 评论 65 点赞

我是靠谱客的博主凶狠豆芽，这篇文章主要介绍【总结】素数筛方法详解前言一、素数的判定二、埃氏筛法三、欧拉筛法四、例题，现在分享给大家，希望可以做个参考。

文章目录

前言
一、素数的判定
二、埃氏筛法
三、欧拉筛法
四、例题

前言

在讲素数筛方法之前，先了解相关知识点：

素数：在大于1的自然数中，除了1和它本身以外不再有其他因数的数。
对于一个合数x,必有一个范围在2~√x 的因数。

素数筛方法主要有三种：

素数的判定（素数筛）
普通线性筛（埃氏筛法 / 埃拉托斯特尼（Eratosthenes）筛法）
优化后的线性筛（欧拉筛法 / 欧拉函数（Euler）筛）

一、素数的判定

时间复杂度：O（√n）

思路： 暴力枚举，很多情况下都会TLE。枚举2~~√n所有数，用n去试着除以，若有能整除的n为合数，若都不能整除，n就是质数了。

复制代码

1
2
3
4
5
6
7
8
9
10
11
int isPrime(int x){
//0和1既不是质数也不是合数 
if(x<2)
return 0;
for(int i=2;i*i<=x;i++){
if(!(x%i))
return 0;
}
return 1;
}

二、埃氏筛法

时间复杂度：O（n loglogn )

思路： 0表示为不是素数，1表示是素数，先全部初始化为1，即先全部标记为素数。0和1均不是素数，然后从2开始，把2的倍数均标记为0，即不是素数，一直到大于n，然后从下一个素数3开始，进行同样的处理，到最后，数组中为1的即为素数。

代码1：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
const int N=1e6;
bool vis[N];
void Erat_Prime(int n){
memset(vis,1,sizeof(vis));
vis[0]=vis[1]=0;	//0和1均不是素数
for(int i=2;i*i<=n;i++){
if(vis[i]){
for(int j=i*i;j<=n;j+=i)
vis[j]=0;
}
}
}

代码2：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool vis[maxn];
int prime[maxn],x;
void Erat_prime(int n) //埃氏筛
{
for(int i=2;i<=n;i++)
{
if(!vis[i]) prime[x++]=i;
for(int j=2;j*i<=n;j++)
{
vis[i*j]=true;
}
}
}

三、欧拉筛法

时间复杂度：O(n)

在用埃式筛法的同时，同一个数字也许会被筛选多次，比如6先被2筛选一次，再被3筛选一次，这样就浪费了很多不必要的时间。欧拉筛法就是在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

用一条语句 if(i%prime[j]==0) break; 避免了重复筛选的发生。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N=1e5+10;
int vis[N];	//0表示素数，1表示非素数
int prime[N];	//只在这个函数有作用
void Euler_prime()
//欧拉筛法
{
for(int i=2;i<=N;i++)
{
if(!vis[i]) prime[x++]=i;
for(int j=0;j<x;j++)
{
if(i*prime[j]>N) break;
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}

四、例题

原题地址：【洛谷】P3383 【模板】线性筛素数

题目描述

如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。

接下来M行每行包含一个不小于1且不大于N的整数，即询问该数是否为质数。

输出格式：

输出包含M行，每行为Yes或No，即依次为每一个询问的结果。

输入输出样例

输入样例#1：

100 5
2
3
4
91
97

输出样例#1：

Yes
Yes
No
No
Yes

说明

时空限制：500ms 128M

数据规模：

对于30%的数据：N<=10000，M<=10000

对于100%的数据：N<=10000000，M<=100000

样例说明：

N=100，说明接下来的询问数均不大于100且不小于1。

所以2、3、97为质数，4、91非质数。

故依次输出Yes、Yes、No、No、Yes。

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e7;
//n表示范围，m表示个数，数组a[i]表示输入的数、数组b[i]，0表示不是为素数，1表示是素数 
int n,m,x,a[N],b[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)	//输入m个数 
scanf("%d",&a[i]);
memset(b,1,sizeof(b));	//初始化，把所有的数标记为是素数 
b[0]=b[1]=0;	//0和1不是素数 
for(int i=2;i<=n;i++)	//从2开始遍历 
{
if(b[i])	//如果标记为素数，即未改变初始化的值 
{
for(int j=i+i;j<=n;j+=i)	//把所有该数的倍数标记为0，即不是素数 
b[j]=0;
}
}
for(int i=1;i<=m;i++)
{
if(b[a[i]])	//如果输入的数是素数，输出Yes 
printf("Yesn");
else	//否则输出No 
printf("Non");
}
return 0;
}