AcWing 196. 质数距离
原题链接
中等
作者:
Anoxia_3
,
2020-07-29 08:24:13
,
所有人可见
,
阅读 506
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000010;
typedef long long LL;
int primes[N] , cnt;
bool st[N];
void init(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()
{
int l , r;
while(cin >> l >> r)
{
init(50000);//因为每次primes[]都会被重新设置,所以每次都要初始化一遍
memset(st , 0 , sizeof st);
for(int i = 0 ; i < cnt ; i++)//二次筛法,用已经求得的1~50000中的质数,筛出所求范围内的质数
{
LL p = primes[i];
for(LL j = max(2 * p , (l + p - 1) / p * p) ; j <= r ; j += p)//每次筛掉p的倍数(1倍除外),
st[j - l] = true;
}
cnt = 0 ;
for(int i = 0 ; i <= r - l ; i++)//重新设置primes[]
if(!st[i] && i + l >= 2) primes[cnt++] = i + l;
if(cnt < 2) puts("There are no adjacent primes.");
else
{
int minp = 0 , maxp = 0;
for(int i = 1 ; i + 1 < cnt ; i++)
{
int d = primes[i + 1] - primes[i];
if(d < primes[minp + 1] - primes[minp]) minp = i;
if(d > primes[maxp + 1] - primes[maxp]) maxp = i;
}
{
printf("%d,%d are closest, %d,%d are most distant.\n" ,
primes[minp] , primes[minp + 1] ,
primes[maxp] , primes[maxp + 1]);
}
}
}
return 0;
}