#yyds干货盘点#素数距离-暗黑源码库

作者：Linux猿简介：CSDN博客专家，华为云享专家，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！关注专栏：Linux 技术（优质好文持续更新中……）欢迎小伙伴们点赞、收藏⭐、留言题目链接~~> 做题感悟：这题是在学习了区间筛法后才做的，学习了区间筛素数后，这题真 so easy ! 解题思路：可以用两次筛法，也可以直接用区间平移。代码： #include #include #include

#include #include #include #include #include #include #include #include using namespace std ; #define LEN sizeof(struct node) #define lld long long int const double PI = 3.1415926535898 ; const double INF = 99999999 ; const long long mod= 1000 ; const int MX = 1000005 ; bool is_prime[MX] ; int prime[MX],num ; void search_prime(int L,int U) { num=0 ; int n=sqrt(1.0*U),j ; int d=U-L+1 ; // 区间长度 memset(is_prime,false,sizeof(is_prime)) ;// 先默认全部为素数 for(int i=( L%2 != 0 ) ;i<d ;i+=2) // 把区间中的偶数筛掉 is_prime[i]=true ; for(int i=3 ;iL&&is_prime[i-L])// 如果 i 大于 L且is_prime[i-l] 为真则必为合数 continue ; j=(L/i)*i ;// j 为最接近L 的和数且为 i的倍数 if(j<L) j+=i ; if(j==i) j+=i ; j-=L ; for( ;j<d ;j+=i) // j每次加 i 均为合数：j=(L/i)*i+i+i…… is_prime[j]=true ; } if(L<=1) is_prime[1-L]=true ;// 0 1 均不是素数 if(L<=2) is_prime[2-L]=false ; for(int i=0 ;i<d ;i++) if(!is_prime[i]) prime[num++]=i+L ; } void find() { int min=9999999,max=0 ; int a1=-1,a2=-1,a3=-1,a4=-1 ; for(int i=1 ;i<num ;i++) { int mx=prime[i]-prime[i-1] ; if(mxmax) { a3=prime[i-1] ; a4=prime[i] ; max=mx ; } } if(a1==-1) printf("There are no adjacent primes.\n") ; else printf("%d,%d are closest, %d,%d are most distant.\n",a1,a2,a3,a4) ; } int main() { int L,U ; while(~scanf("%d%d",&L,&U)) { search_prime(L,U) ; find() ; } return 0 ; } 代码（二次筛法）： #include #include #include

#include #include #include #include #include #include #include #include using namespace std ; #define LEN sizeof(struct node) #define lld long long int const double PI = 3.1415926535898 ; const double INF = 99999999 ; const long long mod= 1000 ; const int MX = 1000005 ; int num=0 ; bool is_prime[MX] ; __int64 prime[MX] ; __int64 prime2[MX] ; void init() // 用筛法筛出第一批素数，用于筛指定区间的素数 { num=0 ; memset(is_prime,false,sizeof(is_prime)) ; for(__int64 i=2 ;i<MX ;i++) { if(!is_prime[i]) prime[num++]=i ; for(int j=0 ;j<num&&i*prime[j]<MX ;j++) { is_prime[i*prime[j]]=true ; if(i%prime[j]==0) break ; } } } void search_prime(__int64 L,__int64 U) { memset(is_prime,false,sizeof(is_prime)) ; for(int i=0 ;i<num&&prime[i]*prime[i]<=U ;i++) { __int64 p=prime[i] ; for(__int64 j=(L+p-1)/p ;p1) is_prime[j*p-L]=true ; } if(L<=1) is_prime[1-L]=true ; if(L<=2) is_prime[2-L]=false ;// 巧妙 int nx=0 ; for(__int64 i=L ;i<=U ;i++) if(!is_prime[i-L]) prime2[nx++]=i ; // 存区间的素数 __int64 min=99999999,max=0,a1=-1,a2=-1,a3=-1,a4=-1 ; for(int i=1 ;imx) { a1=prime2[i-1] ; a2=prime2[i] ; min=mx ; } if(max<mx) { a3=prime2[i-1] ; a4=prime2[i] ; max=mx ; } } if(a1!=-1) printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",a1,a2,a3,a4) ; else printf("There are no adjacent primes.\n") ; } int main() { __int64 L,U ; init() ; while(~scanf("%I64d%I64d",&L,&U)) { search_prime(L,U) ; } return 0 ; } CSDN博客专家，华为云享专家，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！欢迎小伙伴们点赞、收藏⭐、留言

相关推荐