#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++、面试、刷题、算法尽管咨询我,关注我,有问题私聊! 欢迎小伙伴们点赞、收藏⭐、留言

锦绣源码库是一家优秀的网站源码学习交流平台,为广大源码爱好者提供优质的小程序源码、APP源码、H5源码、商城源码教程以及公众号模块教程,大部分是会员免费,网站长期受到各站长的收藏及浏览。
用户必须遵守《计算机软件保护条例(2013修订)》第十七条:为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。鉴于此条例,用户从本平台下载的全部源码(软件)教程仅限学习研究,未经版权归属者授权不得商用,若因商用引起的版权纠纷,一切责任均由使用者自行承担,本平台所属公司及其雇员不承担任何法律责任。
锦绣源码库 » #yyds干货盘点#素数距离
赞助VIP 享更多特权,立即登录下载海量资源
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡