P3383 【模板】线性筛素数

题目

P3383 【模板】线性筛素数 ## 题目描述

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

输入格式

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

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

输出格式

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

数据范围

对于 \(100\%\) 的数据，\(n = 10^8,1≤q≤10^6\)，保证查询的素数不大于\(n\)。

知识/题解

这题是一道筛法模版题，第一个先想到的应该是暴力枚举，但是暴力枚举时间复杂度显然太高，然后经过一番搜寻，找到了埃式筛。

埃式筛

这个筛法的时间复杂度为\(O(n\log\log n)\),算的上是比较优秀了。

如果\(x\)是合数，那么\(x\)的倍数也一定是合数。

这个规则很容易就知道了是对的，是吧，这样我们要求100以内的数就只需将1到10以内的倍数枚举并标记，没有标记的数就是质数，这个筛法就是这个思想。
埃式筛的代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Eratosthenes(int n) {
  int p = 0;
  for (int i = 0; i <= n; ++i) is_prime[i] = 1;
  is_prime[0] = is_prime[1] = 0;
  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      prime[p++] = i;  // prime[p]是i,后置自增运算代表当前素数数量
      if ((long long)i * i <= n)
        for (int j = i * i; j <= n; j += i)
          // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i
          // 的倍数开始，提高了运行速度
          is_prime[j] = 0;  // 是i的倍数的均不是素数
    }
  }
  return p;
}

但是这个还是有点慢，这个数据可能会过不了，所以我们又找到了另一个更快的算法：欧拉筛（线性筛）。

线性筛

埃氏筛法仍有优化空间，它会将一个合数重复多次标记，所以线性筛就是来解决这个事情的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void init() {
  for (int i = 2; i < MAXN; ++i) {
    if (!vis[i]) {
      prime[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * prime[j] >= MAXN) break;
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        // 换言之，i 之前被 pri[j] 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是
        // pri[j] 的倍数 它们都被筛过了，就不需要再筛了，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

本题AC代码

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
#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

bool visited[100000010];
int prime[6000010];

void shai(int n){
	int cnt = 0;
	for(int i = 2;i<=n;i++)
	{
		if(!visited[i])	prime[cnt++] = i;
		for(int j=0;j<cnt;j++){
			if(i * prime[j] > n)
				break;
			visited[i * prime[j]] = 1;

			if(i % prime[j] == 0)
				break;
		}
	}
}

int main()
{
	int n,m,x;
	cin>>n>>m;
	shai(n);

	for(int i=0;i<m;i++)
	{
		scanf("%d",&x);
		printf("%d\n",prime[x-1]);
	}
	getchar();getchar();
	return 0;
}