质数专题

（一）基本概念

定义

恰有两个正约数（1和它本身）的正整数叫作质数（又称素数）

质数分布定理

小于 $x$ 的质数的个数约为 $\frac{x}{\ln x}$

（二）两种筛法

埃氏筛法

时间复杂度： $O(n \log \log n)$

线性筛法

思路：由于埃氏筛还是会将同一个数标记多次（如 $24$ 会被 $2,3,4$ 标记，所以我们要想办法尽可能让次数变为 $1$ 。

代码（模板 P3383 ）：

# include<iostream>
# include<cstdio>
using namespace std;

const int M=1e8+5;
int n,q,k;
bool v[M];
int p[M/20],cnt=0;

void primes(int n){
	for(int i=2;i<=n;++i){
		if(!v[i]) p[++cnt]=i;
		for(int j=1;j<=cnt&&i*p[j]<=n;++j){
			v[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}

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

注解：prime函数中的 i%p[j]==0 也是为了避免重复筛，如果删去，那么 $12$ 会被标记 $2$ 次（当 $i=4,6$ 时各一次）。

时间复杂度： $O(n)$

（三）例题

1. 质数对

· 题面

在区间 $[L,R]$ 中，找出两对质数对 $(p,q)$ 使得：

（1）两对数都是相邻的质数，且都满足 $L \leq p < q \leq R$；

（2）第一对数使得 $q-p$ 最小，而第二对数使得 $q-p$ 最小。

数据范围： $1 \leq L < R \leq 2^{31} , R-L \leq 10^6$ 。

· 分析

首先，对于任意一个在 $[L,R]$ 内的合数 $x$ 必有一个素因子 $p$ 满足 $p \leq \sqrt R$ ，那么我们可以筛出在 $[1,\sqrt R]$ 的所有质数，然后标记这些质数在 $[L,R]$ 内的倍数。容易证明被标记的数就是 $[L,R]$ 内的合数，那么剩下的就是质数（特判 $L=1$ 的情况，此时 $1$ 不是质数）。然后进行线性查找打擂台即可。

时间复杂度： 标记 $O(\sqrt R)$ ，打擂台 $O(R-L)$ ，总的时间复杂度为 $O(\sqrt R+R-L)$ 。

2. 轻拍牛头

· 题面

给定 $ n \in \mathbb N_+ \ (n \leq 10^5), x \in \mathbb N_+ \ (x \leq 10^6) $ 和 $n$ 个正整数 $ a_1,a_2, \cdots a_n \ (a_i \leq x, i=1,2, \cdots ,n) $ 。对于每个 $a_i \ (i=1,2, \cdots ,n)$ ，输出一个 $p \in \mathbb N$ 表示 $a_1,a_2, \cdots a_n$ 中有 $p$ 个 $a_i \ (i=1,2, \cdots ,n)$ 的除自己外的因数。

· 分析

暂无

时间复杂度： $O(n \log x)$

3. CF776B Sherlock and His Girlfriend

· 题面

题目传送门

给定 $n \in \mathbb Z \ (2 \leq n \leq 10^5)$ ，现将数 $2,3, \cdots,n,n+1$ 进行编号，若 $i$ 是 $j$ 的素因子，则 $i, j$ 不同色。输出编号个数的最小值和此时每个数的编号（输出其中一种编码方式即可）。

· 分析

很显然的一种方式，质数和 $1$ 使用一个编号，合数使用另一个编号，注意对 $n=2,3$ 时的情况进行特判。

（四）练习

P1069 P1463 P4446