素数筛 RE 求调(
查看原帖
素数筛 RE 求调(
511609
无钩七不改名楼主2023/5/20 15:05

rt.

#include<bits/stdc++.h>
using namespace std;

int l,r;
int pri[100005],m;
bool b[100005],zs[1000005];

void is_prime(){
	//memset(zs,0,sizeof(zs));
	b[1]=1;
	for(int i(2);i*i<=40005;i++){
		//if(b[i])continue;
		if(!b[i])pri[++m]=i;
		for(int j=2;j<=m&&pri[j]*i<=40005;j++){
			b[i*pri[j]]=1;
			if(i%pri[j]==0)break;
		}
	}
	/*
	int lst=-1,minn=0,mil=0,mir=0,maxn=0,mxl=0,mxr=0;
	for(int i(r-l);i>=0;i--){
		//cout<<i+l<<" "<<zs[i]<<endl;
		if(zs[i])continue;
		if(lst>=0){
			if(minn==0||minn>=lst-i){
				minn=lst-i;
				mil=i;mir=lst;
			}
			if(maxn<=lst-i){
				maxn=lst-i;
				mxl=i;mxr=lst;
			}
		}
		lst=i;
	}
	if(minn==0)puts("There are no adjacent primes.");
	else printf("%d,%d are closest, %d,%d are most distant.\n",mil+l,mir+l,mxl+l,mxr+l);
	*/
	return;
}

void sol(){
	memset(zs,0,sizeof(zs));
	//cout<<1<<endl;
	for(int i(1);i<=m;i++){
		for(int j=l/pri[i];j<=r/pri[i];j++){
			long long x=pri[i]*j;
			if(j>1&&x>=l)zs[x-l]=1;
		}
	}
	//cout<<2<<endl;
	int lst=-1,minn=0,mil=0,mir=0,maxn=0,mxl=0,mxr=0;
	for(int i(r-l);i>=0;i--){
		//cout<<i+l<<" "<<zs[i]<<endl;
		if(zs[i])continue;
		if(lst>=0){
			if(minn==0||minn>=lst-i){
				minn=lst-i;
				mil=i;mir=lst;
			}
			if(maxn<=lst-i){
				maxn=lst-i;
				mxl=i;mxr=lst;
			}
		}
		lst=i;
	}
	if(minn==0)puts("There are no adjacent primes.");
	else printf("%d,%d are closest, %d,%d are most distant.\n",mil+l,mir+l,mxl+l,mxr+l);
	return;
}

int main(){
	//cout<<(1<<15)<<endl;
	while(scanf("%d%d",&l,&r)){
		is_prime();
		sol();
	}
    return 0;
}

调半天了 ,thx qwq

2023/5/20 15:05
加载中...