Prime Distance

​​傳送門​​

題意：

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll pri[100010];
ll vis[100010];
int cnt;
void oula()
{
  for(int i = 2; i <= 50000; i++)
  {
    if(!vis[i])pri[++cnt] = i;
    for(int j = 1; j <= cnt && pri[j]*i <= 50000; j++)
    vis[pri[j]*i] = 1;
  }
}
unordered_map<ll,ll>vis2;
ll ans[1000010];

int main()
{
  oula();
  int t;
  cin>>t;
  while(t--)
  {
    vis2.clear();
    ll l,r;
    scanf("%lld%lld",&l,&r);
    for(ll i = 1; i <= cnt; i++)
    {
      ll j = 2;
      j = max(j,l/pri[i]-1);
      for(; j*pri[i]<=r; j++)
      vis2[j*pri[i]] = 1;
    }
    ll minn = 1e6,now = 0,f_ans = 0,s_ans = 0;
    ll maxx = 0,m_now=0,m_f_ans=0,m_s_ans=0;
    int num = 0;
    vis2[1] = 1;
    for(ll i = l; i <= r; i++)
    {
      if(!vis2[i])ans[++num] = i;
    }
    for(int i = 2; i <= num; i++)
    {
      if(ans[i]-ans[i-1] > maxx)
      maxx = ans[i]-ans[i-1],m_f_ans=ans[i-1],m_s_ans=ans[i];
      if(ans[i]-ans[i-1] < minn)
      minn = ans[i]-ans[i-1],f_ans=ans[i-1],s_ans=ans[i];
    }
    if(f_ans&&s_ans)
    printf("%d,%d are closest, %d,%d are most distant.\n",f_ans,s_ans,m_f_ans,m_s_ans);
    else cout<<"There are no adjacent primes.\n";
  }
}