POJ-2689 求调
  • 板块学术版
  • 楼主Rosent
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/1/22 15:29
  • 上次更新2024/1/22 18:25:48
查看原帖
POJ-2689 求调
651793
Rosent楼主2024/1/22 15:29

rt

#include <cstdio>
#include <iostream>
#define int long long
using namespace std;
int pri[100010];
int chck[100010];
int t=0;
void prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!chck[i])
            pri[++t]=i;
        for(int j=1;i*pri[j]<=n&&j<=t;j++)
        {
            chck[i*pri[j]]=1;
            if(i%pri[j]==0)
                break;
        }
    }
    return ; 
}
int a[1000010];
signed main()
{
	prime(100000);
	int l,r;
	while(cin>>l>>r)
	{
		for(int i=1;i<=t;i++)
		{
			for(int j=l/pri[i];j<=r/pri[i];j++)
			{
				if(j<=1) continue;
				a[j*pri[i]-l]=1;
	//			cout<<j*pri[i]<<" ";
			}
		}
		if(l==1) a[0]=1;
		if(l==0) a[0]=a[1]=1;
		int maxd=-1,mind=2147483647,lastp=-1,cnt=0,max1,max2,min1,min2;
		for(int i=0;i<=r-l;i++)
		{
			if(!a[i]){
				lastp=i;
				++cnt;
				break;
			}
		}
		for(int i=lastp+1;i<=r-l;i++)
		{
			if(!a[i])
			{
				if(i-lastp>maxd)
				{
					max1=lastp+l;
					max2=i+l;
					maxd=i-lastp;
				}
				if(i-lastp<mind)
				{
					if(i==lastp) continue;
					min1=lastp+l;
					min2=i+l;
					mind=i-lastp;
				}
				lastp=i;
				cnt++;
			}
			a[i]=0;
		}
		if(cnt<2)
			puts("There are no adjacent primes.");
		else
			printf("%lld,%lld are closest, %lld,%lld are most distant.\n",min1,min2,max1,max2);
	}
	
	return 0;
}

2024/1/22 15:29
加载中...