【题目链接】

ybt 1619：【例 1】Prime Distance
LOJ 10197. 「一本通 6.2 例 1」Prime Distance

【题目考点】

1. 筛法求质数：埃筛、欧拉筛

相关知识见：
ybt 2040：【例5.7】筛选法找质数

【解题思路】

直观的思路是：将区间$[L,R]$中所有质数添加进顺序表v中，遍历顺序表即可求出相邻质数差值最大的数对和差值最小的数对。

而筛法只能求1~n中的所有质数，本题$L、R<2^{31}$，也就是会达到$10^9$量级。
以$O(n)$的线性筛求$1\sim 10^9$中的所有质数，也会超时。

而本题具有特征$R-L\le 10^6$。因此可以考虑只对区间$[L,R]$进行筛法求质数，筛掉其中的合数，剩下的就是质数。

根据对埃筛的认识，要想筛掉区间$[1,n]$中的所有合数，需要筛掉$[2,\sqrt{n}]$中所有质数的倍数（2倍及以上）。
因此要想筛掉区间$[L,R]$中的合数，需要筛掉$[2,\sqrt{R}]$中所有质数的倍数。
而$R<2^{31}<2.5\ast 10^9$，那么$\sqrt{R}\le 50000$。
所以只需要先求出区间$[1,50000]$中所有的质数。而后对区间$[L,R]$筛掉所有区间$[1,50000]$中质数的倍数，剩下的就是区间$[L,R]$中的质数。

首先通过埃筛或线性筛求出区间$[1,50000]$中所有的质数，
枚举其中的每个质数，对于其中第i个质数记为$p_i$，筛掉区间$[L,R]$中$p_i$的倍数。

求大于等于$L$的最小的$p_i$的倍数，设该数为$k\cdot p_i$，那么$k\cdot p_i\ge L$
所以$k\ge \frac{L}{p_i}$， $k$的最小取值为$\lceil \frac{L}{p_i}\rceil$
因此大于等于$L$的最小的$p_i$的倍数为$\lceil \frac{L}{p_i}\rceil p_i$
求小于等于$R$的最大的$p_i$的倍数，设该数为$k\cdot p_i$，那么$k\cdot p_i\le R$
所以$k\le \frac{R}{p_i}$，$k$的最大取值为$\lfloor \frac{R}{p_i}\rfloor$
因此，小于等于$R$的最大的$p_i$的倍数为$\lfloor \frac{R}{p_i}\rfloor p_i$

设$j$表示$p_i$的倍数，要想使$L\le j\cdot p_i\le R$，那么$j\in [\lceil \frac{L}{p_i}\rceil ,\lfloor \frac{R}{p_i}\rfloor ]$。枚举$[\lceil \frac{L}{p_i}\rceil ,\lfloor \frac{R}{p_i}\rfloor ]$范围内所有$j$的值，将$j\cdot p_i$筛掉。特殊地，当$j$为1时，取到的值为$p_i$，是质数 ，不用筛掉。

由于$j\cdot p_i$的取值最大可以达到$10^9$，无法作为数组下标，即无法直接设数组isPrime[i]表示i是否为质数。此处可以利用性质$R-L\le 10^6$，只表示该范围内的数是否为质数。设布尔型数组dip，数组长度为$10^6$。dp[i]表示$L+i$是否为质数，或者可以描述为dip[i-L]表示$i$是否为质数。
同时，如果$L$为1，则应该特殊地设置1不是质数，即dip[1-1]=dip[0]=false

筛掉区间$[L,R]$中所有质数的倍数后，遍历$[L,R]$区间，将其中的质数取出，添加到一个顺序表(vector)中。如果顺序表长度小于2，则输出“没有质数对”。否则后遍历顺序表，求出相邻质数差值最大的数对和差值最小的数对。

注意：L、R的取值可能达到$2^{31}-1=2147483647$，部分运算的结果可能会超过int类型的范围，应该设为long long类型。

【题解代码】

#include<bits/stdc++.h>
using namespace std;
#define N 50005
bool isPrime[N], dip[1000005];//dip[i]：i+l是否是质数 
int prime[N], pn, l, r;
void initPrime(int n)//线性筛1~n中的质数 
{
	memset(isPrime, 1, sizeof(isPrime));
	for(int i = 2; i <= n; ++i)
	{
		if(isPrime[i])
			prime[++pn] = i;
		for(int j = 1; j <= pn && i*prime[j] <= n; ++j)
		{
			isPrime[i*prime[j]] = false;
			if(i%prime[j] == 0)
				break;
		}
	}
}
long long divCeil(long long a, long long b)
{
	return (a+b-1)/b;
}
bool getIsPrime(long long i)//判断数值i是否是质数 
{
	return dip[i-l];
}
void setIsPrime(long long i, bool val)//设置数值i是否质数 
{
	dip[i-l] = val;
}
int main()
{
	initPrime(50000);
	while(cin >> l >> r)
	{
		memset(dip, 1, sizeof(dip));
		for(int i = 1; i <= pn; ++i)
			for(int j = divCeil(l, prime[i]); j <= r/prime[i]; ++j) if(j > 1)
				setIsPrime((long long)j*prime[i], false);
		if(l == 1)
			setIsPrime(1, false);
		vector<int> v;
		for(long long i = l; i <= r; ++i) if(getIsPrime(i))
			v.push_back(i);
		if(v.size() < 2) 
			cout << "There are no adjacent primes." << endl;
		else
		{
			int mnl, mxl, mnv = 2e9, mxv = 0;
			for(int i = 0; i <= v.size()-2; ++i)
			{
				if(v[i+1]-v[i] > mxv)
					mxv = v[i+1]-v[i], mxl = i;
				if(v[i+1]-v[i] < mnv)
					mnv = v[i+1]-v[i], mnl = i;
			}
			cout << v[mnl] << ',' << v[mnl+1] << " are closest, " 
			     << v[mxl] << ',' << v[mxl+1] << " are most distant." << endl;
		}
	} 
	return 0;
}