题目
题解思路
大合数N必然存在一个质因子小于等于根号N,不然怎么组合出他。
所以我们只需筛出2到根号R的素数,再用这个区间的素数来筛出区间里的素数。
将区间的每个素数减去l来存入数组寻找差值。(类似离散化吧)
时间复杂度Nloglogn(因为我用的埃式筛 感觉和欧拉筛差不了多少)约等于On
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10 ;
bool pre[N] ;
int vis[N];
long long l ,r ;
void in()
{
pre[1] = 1 ;
for (long long i = 2 ; i <= 50000 ; i++ )
{
if ( ! pre[i] )
{
for (int j = i*2 ; j <= 50000 ; j+=i )
pre[j] = 1 ;
for (long long k = max ((l + i - 1 ) / i * i , 2*i) ; k <= r ; k += i )
{
vis[k-l] = 1 ;
}
}
}
}
int main ()
{
ios::sync_with_stdio(false);
while( cin >> l >> r)
{
memset(vis, 0 , sizeof(vis) );
int mi = INF , ma = -1 ;
int t1 = INF , t2 = -1 ;
int mit1 , mit2 , mat1 , mat2 ;
in();
for (int i = 0 ; i <= r - l ; )
{
if ( i == 0 && l == 1 )
{
i++;
continue;
}
if ( vis[i] == 0 )
{
t1 = i + l ;
i++;
while( i <= r - l && vis[i] )
i++;
if ( i <= r - l )
{
t2 = i + l ;
if ( t2 - t1 > ma )
{
mat1 = t1;
mat2 = t2;
ma = t2 - t1 ;
}
if ( t2 - t1 < mi )
{
mi = t2 - t1 ;
mit1 = t1 ;
mit2 = t2 ;
}
}
}else
i++;
}
if ( ma == -1 )
{
cout<<"There are no adjacent primes.\n";
}else
{
cout<<mit1<<","<<mit2<<" are closest, " <<mat1<<","<<mat2<<" are most distant.\n";
}
}
return 0 ;
}