RE 求助!
查看原帖
RE 求助!
751073
wuxiyi楼主2023/3/11 18:11
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int prime[(int)1e6+10],m=0;
bool v[(int)1e6+10]={false},prime2[(int)1e6+10];
void primes(int x)
{
	m=0;
	for (int i=2;i<=x;i++)
	{
		if (!v[i]){
			prime[++m]=i;
			for (int j=i*i;j<=x;j+=i)
			{
				v[j]=1;
			}
		}
	}
	return ;
}
void solve(int l,int r)
{
	memset(prime,0,sizeof(prime));
	memset(v,false,sizeof(v));
	memset(prime2,0,sizeof(prime2));
	primes(sqrt(r));
	for (int i=1;i<=m;i++)
	{
		int p=prime[i];
		for (int j=max(2,(l+p-1)/p);j<=r/p;j++){
			prime2[j*p-l]=1;
		}
	}
	int a1=0,a2=-1,b1=0,b2=0;//min(a2-a1),max(b2-b1)
	int last=-1;
	bool flag=false;
	for (int i=0;i<=r-l;i++)
	{
		if (!prime2[i]){
			
			if (last==-1)
			{
				last=i+l;
			}
			else
			{
				flag=true; 
				if (i+l-last<a2-a1)
				{
					a1=last;
					a2=i+l;
				}
				if (i+l-last>b2-b1)
				{
					b1=last;
					b2=i+l;
				}
				last=i+l;
			}
		}
	}
	if (!flag)	printf("There are no adjacent primes.\n");
	else printf("%d,%d are closest, %d,%d are most distant.\n",a1,a2,b1,b2);
	return ;
}
int main()
{
	int l,r;
	while (cin>>l>>r)
	{
		if (l<2)	l=2;
		solve(l,r);
	}
	return 0;
}
2023/3/11 18:11
加载中...