spoj Prime Generator
发布时间:2020-12-14 04:20:00 所属栏目:大数据 来源:网络整理
导读:题意:判断ll-rr范围内的质数。 一个个用 miller-rabin算法判断 // #pragma comment(linker,"/STACK:1024000000,1024000000") #includeiostream #include cstdio #include string #include cstring #include vector #include cmath #include queue #include
题意:判断ll-rr范围内的质数。 一个个用miller-rabin算法判断 //#pragma comment(linker,"/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include <stack> using namespace std; typedef long long lon; const lon SZ=1000010,INF=0x7FFFFFFF; lon pow(lon x,lon n,lon mod) { lon res=1,ele=x; for(;n;) { if(n&1)res=ele*res%mod; ele=ele*ele%mod; n/=2; } return res; } bool isp(lon x) { if(x==1)return 0; int sz=3; lon arr[sz]={2,7,61}; for(lon i=0;i<sz;++i) { if(x==arr[i])return 1; lon id=x-1; for(;!(id&1)&&id;id/=2); lon m=pow(arr[i],id,x); if(m==1)continue; for(;id!=x-1&&m!=1;) { //if(x==5)cout<<m<<endl; if(m==x-1)break; m=m*m%x; //if(m!=1&&m!=x-1)return 0; id*=2; } if(m!=x-1)return 0; } return 1; } int main() { std::ios::sync_with_stdio(0); //freopen("d:1.txt","w",stdout); lon casenum; cin>>casenum; for(lon time=1;time<=casenum;++time) //for(;scanf("%d",&n)!=EOF;) { lon ll,rr; cin>>ll>>rr; for(lon i=ll;i<=rr;++i) { if(isp(i))cout<<i<<endl; } cout<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |