这里参考于大佬的题解:AcWing 196. 质数距离 - AcWing
前言:由于L,U最大可以取到2^32-1,2^31-1是约等于2e9,如果采用普通的线性筛法的话,无论是时间复杂度还是空间复杂度都是O(n)==O(2e9),那必然是会超时的,那么我们就思考一下怎么做出优化。
分析:由于注意到 L,U 的差值只是1e6,那么采用O(n)或者O(nlogn)的做法
总结一下y总的思路,如下
- 一个合数n的两个因子,必然有一个不会超过sqrt(n),那么sqrt(2^31)≈50000,可以在时间复杂度接受的范围之中
- 如果n是合数,那么一定存在在(1~50000)中间有一个因子P,(1<P<n)
步骤:
- 首先筛选出1~50000内所有的质数
- 运用埃氏筛质数法,1~50000内所有的质数P在[L,R]中的倍数都被染色成为合数,剩下没有被染色的就是质数
埃氏筛质数法:保证一个数只会被他的质因子染色,也就是说用质因子去染色在[L,R]范围内的所有倍数,首先为了避免不必要的操作,需要先计算出在(L,R)范围内,关于质因子p的最小倍数,
也就是L/p (上取整),等价于 L+p-1/p (下取整)。那么在埃氏筛法里面,模板如下
for (int i = 0;i < cnt;i++)
{
int P0 = primes[i];//至少是2倍,不然质数本身会被染色,或者[L/p]倍,所以取最大值
for (ll j = max(0ll + 2 * P0, (l + P0 - 1) / P0*P0);j <= u;j += P0)
{//离散化的步骤,用j-l离散化
st[j - l] = true; //表示j是一个合数
}
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define x first
#define y second
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
bool st[N];
int primes[N];
int cnt;
int mp[N];
ll ans[N];
void print()
{
cout << 1 << ' ';
exit(0);
}
void solve(int n)
{//欧拉筛法
cnt = 0;memset(st, 0, sizeof st);
for (int i = 2;i <= n;i++)
{
if (!st[i]) primes[cnt++] = i;
for (int j = 0;primes[j] <= n / i;j++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main()
{
ll l, u;
while (cin >> l >> u)
{
memset(ans, 0, sizeof ans);
solve(50000);
memset(st, 0, sizeof st);
for (int i = 0;i < cnt;i++)
{
int P0 = primes[i];
for (ll j = max(0ll + 2 * P0, (l + P0 - 1) / P0*P0);j <= u;j += P0)
{
st[j - l] = true; //表示j是一个合数
}
}
cnt = 0;
for (int i = 0;i <= u - l;i++)
{ //由于2不是一个质数,所以要特判一下
if (!st[i]&&i+l>=2) ans[cnt++] = i + l;
}
int maxx = 0, minn = 0;
for(int i=0;i+1<cnt;i++)
{
int d=ans[i+1]-ans[i];
if(ans[maxx+1]-ans[maxx]<d) maxx=i;
if(ans[minn+1]-ans[minn]>d) minn=i;
}
if(cnt<2) printf("There are no adjacent primes.\n");
else
{
printf("%d,%d are closest, %d,%d are most distant.\n",ans[minn],ans[minn+1],ans[maxx],ans[maxx+1]);
}
}
return 0;
}