素数筛

1、素数筛（这应该是最全的总结了，四种基本方法，7种优化方法）-CSDN博客

质数(素数)是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。—“质数(素数)百度百科”

  1. 素数是自然数，因此是整数
  2. 素数是大于1的自然数，因此小于等于1的数字都不是素数（包括负数，0和小数）
  3. 素数只有两个因数，1和自身
  4. 最小的素数是2

对于这类求解素数个数有关的题目，通常采用质数筛算法。

试除法

如果可以被整除，则说明枚举的数字是n的因子。根据素数定义，数字n非素数 如果不可以被整除，则需要继续往后枚举，查看其他枚举数字相除之后的结果 如果后面有可以被整除的数字，则结果和上面第一条一样。 如果在[2，n-1]范围内都没有可以被整除的数字，则说明数字n在[1，n]范围内只有1和n两个因子，因此n是素数。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>
using namespace std;
int IsPrime(int n)
{
    int i;

    if(n<2)
        return 0;
    else
    {
        for(i=2;i<n;i++)
        {
            if(n%i==0)
                return 0;
        }
        return 1;
    }
}

int main()
{
    int n;
	cin>>n;
        if(IsPrime(n)==1)
          cout<<n<<"是素数\n";
        else
          cout<<n<<"不是素数\n";

    return 0;
}

//优化到：
时间复杂度为O(n/2)
    理由是除了1最小的因子是2
 int IsPrime(int n)
{
    int i,m;
    if(n<2)
        return 0;
    else
    {
        m=n/2;//其他代码都没有变，只是这里范围变动了一下
        for(i=2;i<=m;i++)
        {
            if(n%i==0)
                return 0;
        }
        return 1;
    }
}

//根据偶数进行优化
//理由是除了2之外的偶数都不是质数
int IsPrime(int n)
{
    int i;
    if(n<2||(n!=2&&n%2==0))
        return 0;
    else
    {
        for(i=3;i<n;i+=2)
        {
            if(n%i==0)
                return 0;
        }
        return 1;
    }
}
//继续优化，结合两者
int IsPrime(int n)
{
    int i,m;
    if(n<2||(n!=2&&n%2==0))
        return 0;
    else
    {
        m=n/2;
        for(i=3;i<m;i+=2)
        {
            if(n%i==0)
                return 0;
        }
        return 1;
    }
}

//平方根优化
//原因是：
//成对出现的两个因子相乘等于原来的数字，并且成对出现的因子分布在sqrt(n)的两侧
//因为因子是成对出现，并且分布在sqrt(n)两侧。那么判断数字有无其他因子的时候，判断范围可以从[2，n-1]缩小到[ 2，sqrt(n) ]。（如果[2， sqrt(n) ]没有因子，那么[ sqrt(n) ， n-1]也不会有因子。原因就是前面提到的，因子是成对出现的）
int IsPrime(int n)
{
    int i,m;
    if(n<2)
        return 0;
    else
    {
        m=(int)sqrt((double)n)
        for(i=2;i<=m;i++)
        {
            if(n%i==0)
                return 0;
        }
        return 1;
    }
}
//另一种写法
//不算优化
int IsPrime(int n)
{
    int i;
    if(n<2)
        return 0;
    else
    {
        for(i=2;i*i<=n;i++)
        {
            if(n%i==0)
                return 0;
        }
        return 1;
    }
}
//结合以上所有，得到试除法最后的优化
int IsPrime(int n)
{
    int i;
    if(n<2||(n!=2&&n%2==0))
        return 0;
    else
    {
        for(i=3;i*i<=n;i+=2)
        {
            if(n%i==0)
                return 0;
        }
        return 1;
    }
}

埃式筛法(埃拉托斯特尼筛法)

上面的算法我们是尝试把数字拆分为因子相乘的形式，对范围区间内的数字进行判断时，，则需要对每个数字都进行拆分。

我们可以逆向思考，我们想办法把合数筛出去，剩下的不就是素数了嘛？

其中

1
vis[i]=1//表示这个数是合数
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
const int  maxn= 20010;

int vis[maxn];//vis用来判断数字是否访问过
int prime[maxn];//prime用来存储筛选出来的素数
void sieve(int n)
{
    int i,j,k;
    k=0;
    memset(vis,0,sizeof(int)*maxn);//将访问数组清零。可以使用short或者C++的bool类型节省内存
    vis[0]=vis[1]=1;//将0和1标记为已访问，不标记其实也可以，因为我们素数的计数是从2开始
    for(i=2;i<=n;i++)//从最小的素数2开始筛选，2以下就没必要筛选
    {
        if(vis[i]==0)//这个数是目前最小的，且未被访问过的
            prime[k++]=i;//因此这个数是素数
        for(j=2;i*j<=n;j++)//j表示倍数，从两倍开始倍增，直到上界为止
            vis[i*j]=1;//将倍数标记为已访问
    }
}

//另外一种写法
void sieve(int n)
{
    int i,j,k;
    k=0;
    vis[0]=vis[1]=1;
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)
            prime[k++]=i;
        for(j=i+i;j<=n;j+=i)//这里j表示i的倍数结果，每次加i相当于加一倍
            vis[j]=1;
    }
}

//优化
/*原因：数学定理–唯一分解定理，也是算术基本定理
算术基本定理可表述为：任何一个大于 1 的自然数 N, 如果 N 不为**质数**，那么 N 可以唯一分解成有限个质数的乘积
因此：对最小的素数进行倍增之后，就不需要对其倍数结果进行倍增。
即对3进行倍增之后，就不在需要对6,9,12进行倍增
*/
//区别就是如果是素数才进行倍增，上一个是什么数字都倍增了
void Eratosthenes_sieve(int n)//这里用了英文全称，平时用sieve等命名就好
{
    int i,j,k;
    k=0;
    memset(vis,0,sizeof(int)*maxn);
    vis[0]=vis[1]=1;
    for(i=2;i<=n;i++)//从最小的素数2开始筛选，2以下就没必要筛选
    {
        if(vis[i]==0)//这个数是目前最小的，且未被访问过的
        {
            prime[k++]=i;//因此这个数是素数,存储起来
            for(j=2;i*j<=n;j++)//这里的改变就是把损坏放入if判断语句之内
                vis[i*j]=1;//只对素数进行倍增筛选，其他基本不变
        }
    }
}
//又是一个小优化，j不应该从2开始，而应该从i
//因为2，3早就在i前枚举过了，不需要再枚举，因此可以小优化
void Eratosthenes_sieve(int n)
{
    int i,j,k;
    k=0;
    memset(vis,0,sizeof(int)*maxn);
    vis[0]=vis[1]=1;
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)
        {
            prime[k++]=i;
            for(j=i;i*j<=n;j++)
                vis[i*j]=1;
        }
    }
}
//结合第一个方法还能优化：
//埃氏素数筛函数
void Eratosthenes_sieve(int n)
{
    int i,j,k;
    k=0;
    memset(vis,0,sizeof(int)*maxn);
    vis[0]=vis[1]=1;
    vis[2]=0;
    prime[k++]=2;
    for(i=3;i<=n;i+=2)
    {
        vis[i+1]=1;
        //偶数标记
        //应该是小优化，砍去一半
        if(vis[i]==0)
        {
            prime[k++]=i;
            for(j=i;i*j<=n;j++)
                vis[i*j]=1;
        }
    }
}

欧拉筛

埃氏筛有一个问题，就是一个数字可能会被重复筛除。比如说12，可能在2的时候被筛除，可能在6的时候被筛除。即使进行了上面的优化(只对素数进行倍增)，也还是会被3筛除。

欧拉筛就是要解决这个问题，保证每个合数只被筛选一次，从而提高效率和运行速度

由于上述定理：每个合数都有一个最小素因子

让每个合数被其自身的最小素因子筛选，而不会被重复筛选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//欧拉筛函数
void Euler_sieve(int n)
{
    int i,j,k;
    k=0;//保存素数的个数
    memset(vis,0,sizeof(int)*maxn);//初始化数组
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)//i是素数，则存起来
            prime[k++]=i;
        for(j=0;j<k;j++)//进行倍增，用i去乘以i之前(包括i)的素数
        {
            if(i*prime[j]>n)//倍增结果超出范围，退出
                break;

            vis[ i*prime[j] ]=1;//将倍增结果进行标记

            if(i%prime[j]==0)//i是前面某个素数的倍数时，也需要退出
                break;
        }
    }
}

题目

【模板】线性筛素数

题目背景

本题已更新，从判断素数改为了查询第 \(k\) 小的素数
提示：如果你使用 cin 来读入，建议使用 std::ios::sync_with_stdio(0) 来加速。

题目描述

如题，给定一个范围 \(n\)，有 \(q\) 个询问，每次输出第 \(k\) 小的素数。

输入格式

第一行包含两个正整数 \(n,q\)，分别表示查询的范围和查询的个数。

接下来 \(q\) 行每行一个正整数 \(k\)，表示查询第 \(k\) 小的素数。

输出格式

输出 \(q\) 行，每行一个正整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5
6
100 5
1
2
3
4
5

样例输出 #1

1
2
3
4
5
2
3
5
7
11

提示

【数据范围】
对于 \(100\%\) 的数据，\(n = 10^8\)，\(1 \le q \le 10^6\)，保证查询的素数不大于 \(n\)。

Data by NaCly_Fish.

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
34
35
//by dpcc
#include<bits/stdc++.h>
using ll=long long;
using namespace std;
#define r0 return 0;
#define  re register
#define rep(i,a,n) for(re int i=a;i<=n;i++)
#define frep(i,a,n) for(re int i=a;i>=n;i--)
int n,x;
const int N=1e8+10;
bool pd[N];
int ans[N];
int n2;
int main(){
	pd[1]=1;
cin>>x>>n;
for(int i=2;i<=x;i++)
{
	if(!pd[i]) ans[++n2]=i;//记录下来
	for(int j=1;j<=n2&&i*ans[j]<=x;j++)
	{
		//此时的素数的个数
		pd[ans[j]*i]=1;
		if(i%ans[j]==0)//退出避免多筛选
		break;
	}
}
rep(i,1,n)
{
	int h;
	cin>>h;
cout<<ans[h]<<'\n';
}
	r0
}