SPOJ PRIME1 - Prime Generator【Miller_Rabin

2019-04-14 18:48发布

站内文章 / 模拟电子
16887 0 1283
之前切了一道模板题，发现没发上来，直接miller_rabin就好，某度上的讲解都挺好……算了还是写几句好了233 嗯……根据费马小定理，模素数p的意义下，一个数a的p-1次方肯定是1……然而直接用这个判断会出锅【原因我不管了QwQ 于是，平方是1的数……如果不是模意义下，只有1和-1，稍微手推一下（那么多blog都写了随便找一个就好）会发现……如果是由【非-1的数】取平方得到了1，那么这个模数肯定不是质数 于是直接跑就好……反正正常数据范围下用2,3,5,7,11就够了
#include using namespace std; int t,l,r; const int che[]={2,3,5,7,11}; long long pow(int d,int c,int n){ long long tmp=d,rtn=1; while(c){ if(c&1) rtn*=tmp; tmp*=tmp; rtn%=n; tmp%=n; c>>=1; } return rtn; } bool Miller_Rabbin(int a,int n){ int s=0,d=n-1; while(d&&(!(d&1))) ++s,d>>=1; long long k=pow(a,d,n); if(k==1||k==n-1) return 1; for(int i=1;i<=s;++i){ k=k*k%n; if(k==n-1) return 1; } return 0; } bool is_prime(int n){ if(n==1) return 0; for(int i=0;i<5;++i){ if(n==che[i]) return 1; if(!(n%che[i])) return 0; if(!Miller_Rabbin(che[i],n)) return 0; } return 1; } int main(){ // freopen("orz.out","w",stdout); scanf("%d",&t); while(t--){ scanf("%d%d",&l,&r); for(int i=l;i<=r;++i) if(is_prime(i)) printf("%d ",i); puts(""); } return 0; }

热门文章