编程学习资讯网

Distance(区间素数)埃氏筛法--编程学习网

发布时间:2018-08-16 09:01:52   来源:本站编辑   浏览次数:

这道题的L和R都很大,所以如果直接开一个1~R的数组明显会超时。但是R-L并不大,所以我们考虑把这个区间(L--R)移动到(1--(R-L+1))这个区间再开数组(就是把每个数减L再加1)。接下来先用埃氏筛分(可以自行百度)求出【2,√R】区间的素数,并存在prime数组里。对于prime数组里的每一个质数,求出其在区间(L--R)的倍数并且标记成false(非素数)。那么剩下的区间(L--R)里的数就都是素数咯~然后相邻的比较,求出差最大的和差最小的即可。

注意的细节:1.判断素数的数组(prime是用来储存素数数据的,用long long)isprime[],和 a[] 最好用bool,节省空间。

2.这道题非bool的数据类型最好都开long long的,不然大的数据点会RE。

3.注意左区间是“1”的情况,“1”是非素数。

下面给出代码:(必要的有注释)

复制代码
 1 #include<cstdio>  2 #include<vector>  3 #include<cstring>  4 #include<algorithm>  5 using namespace std;  6 typedef long long ll;  7 ll prime[65537],cnt;//prime存储【2,√R】区间的素数,cnt记录该区间素数个数   8 bool isprime[65537];//isprime:初始判断 【2,√R】区间的素数  9 bool a[1000010];//原区间左右至(1~(R-L+1)) 后,判断素数  10 ll l,r; 11 void ini() 12 { 13 memset(isprime,1,sizeof(isprime)); 14 isprime[0]=isprime[1]=0; 15 memset(a,1,sizeof(a)); 16 } 17 void sushu()//初始用埃氏筛法,筛选 【2,√R】区间的素数 18 { 19 for (ll i=2;i*i<=r;i++) 20  { 21 if (isprime[i]) 22  { 23 prime[cnt++]=i; 24 for (ll j=i*i;j*j<=r;j+=i) 25 isprime[j]=0; 26  } 27  } 28 } 29 void sift()//筛选区间内的素数  30 { 31 for (ll i=0;i<cnt;i++) 32  { 33 ll bm=l/(ll)prime[i]; 34 for (ll j=bm*(ll)prime[i];j<=r;j+=(ll)prime[i]) 35 if ((j)!=(ll)prime[i]) a[j-l+1]=0; 36  } 37 if (l==1) a[1]=0;//注意“1”不是素数  38 } 39 void minus()//相邻素数求差最大和差最小  40 { 41 ll pre=0,minans=9876544431,maxans=0,x1,x2,y1,y2; 42 for (ll i=1;i<=(r-l+1);i++) 43  { 44 if (a[i]) 45  { 46 if (pre) 47  { 48 if (i-pre > maxans) 49 maxans=i-pre,x1=pre,x2=i; 50 if (i-pre < minans) 51 minans=i-pre,y1=pre,y2=i; 52  } 53 pre=i; 54  } 55  } 56 if (maxans && minans!=987654441) 57 printf("%lld,%lld are closest, %lld,%lld are most distant.\n",(ll)y1+l-1,(ll)y2+l-1,(ll)x1+l-1,(ll)x2+l-1); 58 else printf("There are no adjacent primes.\n"); 59 } 60 int main() 61 { 62 while (scanf ("%lld%lld",&l,&r)!=EOF) 63  { 64  ini(); 65  sushu(); 66  sift(); 67  minus(); 68  } 69 return 0; 70 } 
复制代码

 

编程学习网 http://www.javalearns.cn

关注微信号:javalearns   随时随地学Java

或扫一扫

随时随地学Java