管理学 在职研究生,战狼2完整版迅雷,优秀教师推荐材料
这道题的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 }
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论