救、救、蒟、蒻、吧
查看原帖
救、救、蒟、蒻、吧
335094
Lucifero楼主2021/2/4 18:54

改了一下午,吐了

#include <bits/stdc++.h>
#define int long long
using namespace std;
class Dis
{
public:
	int d,l,r;
}minn,maxn;
bool prime[1000001],vis1[1000001],vis2[1000001];
int make1[1000001],make2[1000001];
int ans,cnt1,cnt2;
void linear_prime_build(int n)
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		if (!vis1[i]) make1[++cnt1]=i,prime[i]=true;
		for(j=1;j<=cnt1 && i*make1[j]<=n;j++)
		{
			vis1[i*make1[j]]=true;
			if (i%make1[j]==0) break;
		}
	}
}
void re_title()
{
	memset(prime,false,sizeof(prime));
	memset(vis1,false,sizeof(vis1));
	memset(vis2,false,sizeof(vis2));
	memset(make1,false,sizeof(make1));
	memset(make2,false,sizeof(make2));
	ans=cnt1=cnt2=0;
}
signed main()
{
	//素数距离
	int L,R,k,tL,i,j;
	while(scanf("%lld%lld",&L,&R)!=EOF)
	{
		re_title();
		minn=(Dis){INT_MAX,INT_MAX,INT_MAX};
		maxn=(Dis){INT_MIN,INT_MIN,INT_MIN};
		if (L==1) L=2;
		linear_prime_build(100000);
		for(i=1;i<=cnt1;i++)
		{
			k=make1[i];
			tL=max(k*2,(L+k-1)/k*k);
			for(j=tL;j<=R;j+=k) vis2[j-L+1]=true;
		}
		for(i=1;i<=R-L+1;i++)
			if (!vis2[i]) make2[++cnt2]=i+1;
//		for(i=1;i<=cnt2;i++) printf("%lld ",make2[i]);
//		printf("\n");
		if (cnt2<=2)
		{
			printf("There are no adjacent primes.\n");
			return 0;
		}
		for(i=2;i<=cnt2;i++)
		{
			int d=make2[i]-make2[i-1];
			if (d<minn.d) minn=(Dis){d,make2[i-1],make2[i]};
			if (d>maxn.d) maxn=(Dis){d,make2[i-1],make2[i]};
		}
		printf("%lld,%lld are closest, %lld,%lld are most distant.\n",minn.l,minn.r,maxn.l,maxn.r);
	}
}
2021/2/4 18:54
加载中...