【题解】质数距离
发布时间
阅读量：
阅读量
N4Ig5iBcoKZaAXKBtUBLKIBGIA0IAHTAJgDYBOAVmIA5KAGegOnpppAF9d1MAnPQpgCMAdgDMpGuSHlSlSkzEiRAgI4l2XHpBAAbALQAlNSTGduIDDoBiRkzuJmtlzAEM7+dQ6cWrIAM4eIF4gjuba4EEhYc5+AMIA8vYgouEuOgCyyUJCaX4AClEkubGYMEUOxHmYACYVoVWlOgT1xI2+mAAqre0RAMpxyTEdOgCiQwAsnAC6+DiQqOkgffVCPhFoq71LGJ6YpNU6hquUhyAAIrn4RDpilNLkE/I0ihM0xFNNIADqWzP4AGMUBEgXsdCURiAYFkwSkzgCYcFhGcALaIkIQiLfK5I8FnAAaOIxZwAHujkV9/OS8V8AGbZM7nBlfGrM2YBKC01y6fwwLggenQDkLCL0ZJiHFIPH4AB2mEAJUaAa2VAAxBAhRwJA6p0ugE/igQnwOsgtGcWpA1l1+sNUGIIlNmD1+D1xutxrt0y+RMwlCm+CloQEcp0gG5TQDfimqNWadU6oGJXWIxPadI7hQa9LHExYzRaY5A00aE0nwJa8/HE+yAO7ez6QqqwhgCf1mWWYMMRkWazA51NlovR4Vx9OQQtZzAQXP5jNFlPO4i9yvesUcdn8SAIXgAVxg+FcUBo9H5VaFRsogPgIAAFm4ZUgWzoAII3gAEcQA9jKwLwYGBXAg0O+BCNCZc0WPxiHIfRJWRO8QCVVV8C1RYzXHHshzWIs+hLSc80zUAzV3XM5zQ8tYWIU4vnA/QxT9EhA0wQBD3UAKiDlSfAAhdskMwIhc0HI10NHGwsNdfi8LcITiOncS+JI3EQATf4QAALw1IE103bcQFXIij2IZxVPXLd8C0/AdL0qADI01c0yPIQzLUrc7IsozYxM2NHPU9yHIsfT1Oc0sQBszzLKtAL9SCvzByPXCQB8wzNJCwLvPM3z4pdULjXC1LrLCpL7L5XKnNSyK3IKjzSri4z0t08r8tAWLguHVzh0yqymtsmq/O0m0WoSnK6uSrz+ryvzsrzHr/MSoaLPG4rmpq8auoyjqiqa6L6vG0b2qmsrtoqlz0rWgaGtmw7IC5HkNOdUCSAgoQAGI7kbaCQCDWCVQ40SdBQ51sJEzsdEwidhOi/CSyI6Tl1hMQawiSj6Ae04aIcOidCYlj2IQyMuJLXj9RBrspLxosCNQiGBI5IGJPZEIJk+dlXqERg0lU87eRGtq7NZhrNs57k2dSxbqqGrnOqaoWYs5PnjtW3mLoimXcpFgWxdl3lVdqiWzql9n0q2zWlda3X1Z1yb9e15WqvV42LdMxWpetw3TZZ83Ktt4X7btuWVoOh3erGz21YD7mOaD+WfaD320rds2vdXE6rdDrKQ/d2O/b153U6j7qI8TuOFZT/nHb6mPC7TyP45zguNYz0us6WquTeLmuGsFyOedz/aooThvva7ju6/F5vG/9nui5Hkvq8lzPW8riew770ey9n5u2+Tufe5KxeB+79fXezrf26r1ejf7+P2VUu45ivOaQF3Dtr8vGBXF4W8Xq6V8sBgV8X3fAFdFcAAbnAV0wFhTXVuPQSCT1kYwTRk+JkmMOxmlZJTMmn1zSExwsTTBf0zQzn2hDammAJjbD8GISB1EQD+hxK9OCH1/rplQUTcm3YfrA0kkwrB5MSZsKprCIQ5F2RYGvtFB+/gADWG5dD9lep0GAn9pE/xlLSGANQYC8F/P+OUICQIRAlFApGcIYJ0MQZxL6OD8aCU4bgh0FjsHWJkhidYSx9GUP9HWN+qNmIvnoWabiwpwbMPQd9EKaCGGsNCUEhhPDIlcPQTE/yhDYS0wUsIzel5MBYFcDKcRKMQCdFcBuGoNRXAwH8BeJ8CReBqP4DosBejiD6A8dQvJJj/pmOLA4jCdjuFg3YUQ7wZwxCNKgjAzxIA4EY3acEnG7CWE9PiQs6JdiBkpHIEMxpbjaKwO8feXxtQllmkBqTKJoMeJzPQfgxJRNVkCNSSI5wD8UQbn8GgAE+gZSvgQMA8ZABpXgaAKxoEUXEF5CBXw1DQNk8paB/FAV0S4sQBiqHbPGZM/Z5jzkSXmV03puLFldNWeBIZSKtnSnGW0xC6CUEnLiQw4w+KGFXN+pY2+KzYSaEhAmJp0CAw7JYgg6ZDD/G8LCdmQ5YlGV4NmXw2SqRIbYAeeyAAVhqG4oR6CkDEEwcQvKaCkAmJQoCzh1VkpAPqw1gEoATBNZgM1FqjXWoVZ8qUSsSRHX5KuUAq5wGdnwBuI6pERBPCeKQWgLB6APHYEZG4DAvighAAG4acqaATGhiIGgYhyA6qEKQEQOJeCxoPJCEmSbCohB9NDe4QhiBMAYNIOQHjC1QDjZCH5ZaUp319QAGTOF+ekCqK1MxjS24tER6T+sDZpItXwUQ4g7XFLtEQpkhCkGcXt/Cly3MZu2T6yAPQjsgGOpYAJ51TqXUsFdmA11fA3XKrd/Cd2IL3Qe6dUBj1+BgGe5NF6/BXtuCoW9yQYZLH7QpIdu72mvubUer4rhv2FV/Zgf9IByBLkhHejE6GIhgcHcIJ9/0X2epuB+zAtIEOdo1H+5IIhsNLEwyQUhfAYADu3Q2Z9UHiPvq+BeFMC6NLRFICwBMjNKAiB9DQRmjAm0zshCiGl/HSLUBIUwWQ5ByDECEDQcTAgYOtpBApqd0RqCSB1RQDTWmdOHv00sPoFHF1UeQ+KOjfgGM6HIpCXDqzSCUK1ERw9pGAb5AEIpt9kAbN+EJCF89jmdAofIeuoYfaWPgcwAljjiFoMka+PiYLk7k16cCz8ezGkkNxeSD5xL/CPM4ZS3h8ElWMsoCy9xyEgrQtlZAG5kABwvhedIlmhQ5DwJSHU2N8gKhrNFe7B12LIAUOYlA3V25AhXyjqm18bRiap2FZZNF5NTiJDEEobtuTiJZsdmo7CXrnnlvXd07JkE52YuXac/dvrd3ZIHA22257P65soZq0t1j9YHujspH9xDAPksg7CxFzAZJ9tQ9e+Vx9MPUvggLY9nYSPKMo66+jhVp2NglZ3NDj7sPduvudMAfkNxEBQFIAivwvpZIgbIes/hMx+SsiFLziIJTcdxRCOpig324cHn5HfUAnW53+K1D5+NQh5eM6K1+lXkBFeQnIxrrXER4O66K3Zw3XxsQm8hISc3EQ50Mv+nrk9QhbcK7V479s9u/Dkad6ruDrvEHu8wHZr3muivYiD/7nQhIw9FbnYiZ3SvY/e7bUIBPwe6TJ7d0V+DKfw/LHT37kPee7dFcJNn6bUfZ0ZHL5CBEVeIjQlr0sMkDe/BUmb5gNAvui88aEGAHEcfIQXh7x4/vERB9gGbF3gfOQAD6ffE+j5n8P+fSxB9CGnxPkfK/iBYDn6ngf2+l979H9vjfy+Pf/wz18PoABPPZ+evijHvKXhCRolZSP2q4QUXMvjnFGKXq/3wd+k+EQ3ybeyYAIYBAQ/gkBWA0Bl+A+lAO+8Bo+iBh+OeF4iBp+qe7IRopAHA/Ia2QooWr0/gAIaAMAN4aAtIbyJYhUvOhU18TO/0aYVghUNwSsR4hUrqLsL25aU68whUEA7mAguSWsXs9U+AACU8/MX+5scAYh/M1+mAAAmq+AGvyHxPcPqtIEdrQDQBwEAA题目描述
题目描述
给定两个整数 ，求闭区间[L,R]中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。
输入格式
多组数据。每行两个数L,R。
输出格式
详见输出样例。
样例
样例输入
2 17
14 17
样例输出
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
题目分析
这一道题很明显是素数筛的题，一般做素数筛都用线筛，因为要快一些，这道题也一样。
直接每一次用线筛，筛出在[L,R]这个区间的所有质数，然后再进行枚举比较求出间隔最小与间隔最大的相邻质数。
错误代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int M = 1e8 + 5;
bool flag[M];
int pre[M];
int prime(int l, int r) {
memset(flag, false, sizeof(flag));
memset(pre, 0, sizeof(pre));
int k = 0;
if (l == 1) {
l++;
}
for (int i = 2; i <= r; i++) {
if (!flag[i]) {
k++;
pre[k] = i;
}
for (int j = 1; j <= k && pre[j] * i <= r; j++) {
flag[pre[j] * i] = true;
if (i % pre[j] == 0)
break;
}
}
return k;
// for(int i=1;i<=k;i++){
// printf("%d ",pre[i]);
// }
}
int main() {
int L, R;
while (scanf("%d %d", &L, &R) != EOF) {
int len = prime(L, R);
if (len == 1) {
printf("There are no adjacent primes.\n");
}
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
int minn = 0x3f3f3f3f, maxn = 0;
for (int i = 1; i <= len - 1; i++) {
if (pre[i + 1] - pre[i] < minn && pre[i] >= L) {
x1 = i, x2 = i + 1;
minn = pre[i + 1] - pre[i];
}
if (pre[i + 1] - pre[i] > maxn && pre[i] >= L) {
y1 = i, y2 = i + 1;
maxn = pre[i + 1] - pre[i];
}
}
if (x1 == 0 && x2 == 0 && y1 == 0 && y2 == 0) {
printf("There are no adjacent primes.\n");
continue;
}
printf("%d,%d are closest, %d,%d are most distant.\n", pre[x1], pre[x2], pre[y1], pre[y2]);
}
return 0;
}但是一提交就直接超时爆零了。
之后我就反思为何会超时。首先，主函数里遍历答案这是不可去除的；之后就是线筛函数也不会错。最后，我发现在每次输入L,R之后，都有一次线筛，那万一第一个数据都包含了之后的数据，就不是浪费时间了。
所以我们可以找到数据的极值，即M。在每次输入数据之前都进行一次最大的线筛，则后面的数据就直接使用就可以了。
正确代码
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int M=1e7+5;
bool flag[M],flag1[M];
int pre[M],arr[M];
int k;
void Prime2(){
flag[0]=flag[1]=true;
for(int i=2;i<=M;i++){
if(flag[i]==false){
pre[k++]=i;
}
for(int j=1;j<k&&pre[j]*i<M;j++){
flag[pre[j]*i]=true;
}
}
}
int main(){
int L,R;
Prime2();
while(scanf("%d %d",&L,&R)!=EOF){
if(L==1){
L=2;
}
memset(flag1,false,sizeof(flag1));
for(int i=0;i<k;i++){
int a=(L-1)/pre[i]+1;
int b=R/pre[i];
for(int j=a;j<=b;j++){
if(j>1){
flag1[pre[i]*j-L]=true;
}
}
}
int x1=0,x2=0,y1=0,y2=0;
int minn=0x3f3f3f3f,maxn=-1,p=-1;
for(int i=0;i<=R-L;i++){
if(flag1[i]==false){
if(p==-1){
p=i;
continue;
}
if(i-p<minn){
x1=p+L,x2=i+L;
minn=i-p;
}
if(i-p>maxn){
y1=p+L,y2=i+L;
maxn=i-p;
}
p=i;
}
}
if(maxn==-1){
printf("There are no adjacent primes.\n");
continue;
}
printf("%d,%d are closest, %d,%d are most distant.\n",x1,x2,y1,y2);
}
return 0;
}
全部评论 (0)
还没有任何评论哟~