- 高 2029 届信息学竞赛选拔考试
素数距离
-
李泽瑞 LV 2 @ 2026-9-4 20:28:30
using namespace std;
int l[1000010],p[1000010],_p,a,b,c=-1,d=-1;
int main(){
l[0]=1,l[1]=1;
for(int i=2;i<=1000000;i++){
if(l[i]==0) p[++_p]=i;
for(int j=1;j<=_p;j++){
if(i*p[j]>1000000) break;
l[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
scanf("%d%d",&a,&b);
for(int i=a;i<=b;i++){
if(l[i]==0){
c=i;
break;
}
}
for(int i=b;i>=a;i--){
if(l[i]==0){
d=i;
break;
}
}
if(c!=d) printf("%d",d-c);
else printf("No");
return 0;
}
1 comments
-
Myobot @ 2026-9-4 20:28:36
[李泽瑞] 同学，你好。
我看到你使用了欧拉筛（线性筛）预处理了 以内的素数，然后分别从左端和右端寻找第一个素数，最后输出它们的差。
你的预处理部分写得很好，
i % p[j] == 0的跳出条件确保了每个合数只被筛一次，时间复杂度是 的。不过，在主逻辑里，我注意到一个可能被忽略的边界情况：
- 如果
a和b之间只有一个素数，那么c和d会指向同一个数，此时你输出"No"，这是符合题意的吗？ - 如果
a和b之间没有素数呢？你的循环结束后c和d都会保持初始值-1，此时c == d，也会输出"No"。这似乎正确，但请仔细思考：题目要求的是“距离”还是“区间内是否存在素数”？ 如果区间内没有素数，输出"No"是否是最合适的表达？
另外，请你重新审视题目本身：题目叫“素数距离”，它真的只是让你找最左和最右的素数吗？请回忆一下题目的完整描述——它问的是区间内任意两个素数之间的最大距离，还是相邻素数之间的最大间隔？如果是最左和最右，你的代码没问题；但如果是相邻素数之间的最大差值，你的算法可能就需要调整了。
请先确认题意，再告诉我你的想法。
- 如果
- 1