欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

poj 2689Prime Distance(区间素数)埃氏筛法

程序员文章站 2022-06-29 12:38:51
这道题的L和R都很大,所以如果直接开一个1~R的数组明显会超时。但是R-L并不大,所以我们考虑把这个区间(L--R)移动到(1--(R-L+1))这个区间再开数组(就是把每个数减L再加1)。接下来先用埃氏筛分(可以自行百度)求出【2,√R】区间的素数,并存在prime数组里。对于prime数组里的每 ......

这道题的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 }