一份会 RE 的代码
  • 板块灌水区
  • 楼主BHIS_oldsix
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/8/24 14:30
  • 上次更新2024/8/24 16:34:44
查看原帖
一份会 RE 的代码
1002446
BHIS_oldsix楼主2024/8/24 14:30
#include<bits/stdc++.h>
#define int long long
using namespace std;
int L,R,maxx;
int v[1000005];
int prime[2<<16],cnt,last;
int maxl,maxr,minl,minr=1e9;

void primes(int n){
    memset(v,0,sizeof(v));
    for(int i=2;i<=n;i++){
        if(!v[i]){
        	cnt++;
            prime[cnt]=i;
            for(int j=i;j<=n/i;j+=i)
            	v[j]=1; 
        }
   	}
}
int L_prime(int a,int b){
	if(a%b==0)return a/b;
	else return a/b+1;
}
signed main(){
	primes((2<<16));
//	freopen("1.in","r",stdin);
	while(scanf("%d %d",&L,&R)!=EOF){
		if(L==1&&R==2){
			printf("There are no adjacent primes.\n");
			continue;
		}
		
		memset(v,0,sizeof(v));
		
		
		for(int i=1;i<=cnt;i++){
			for(int j=L_prime(L,prime[i]);j*prime[i]+1<=R;j++){
				v[j*prime[i]-L+1]=1;
			}
			if(prime[i]-L+1>=0)
				v[prime[i]-L+1]=0;
		}
		
		for(int i=L;i<=R-L+1;i++){
			if(!v[i-L+1]){
				last=i;
				break;
			}
		}
		maxl=maxr=minl=last;
		minr=1e9;
		for(int i=last+1;i<=R;i++){
			if(v[i-L+1])continue;
			if(i-last>maxr-maxl){
				maxr=i;
				maxl=last;
			}
			if(i-last<minr-minl){
				minr=i;
				minl=last;
			}
			last=i;
		}
		
		if(minr==1e9){
			printf("There are no adjacent primes.\n");
		}
		else{
			printf("%d,%d are closest, %d,%d are most distant.\n",minl,minr,maxl,maxr);
		}
		
	}
	return 0;
}
2024/8/24 14:30
加载中...