#include <iostream> #include <cstdlib> #include <ctime> using namespace std; long long mulmod(long long a,long long b,long long c){u long long x = 0,y=a%c; while(b > 0){ if(b%2 == 1){ x = (x+y)%c; } y = (y*2)%c; b /= 2; } return x%c; } int modulo(int a,int b,int c){ long long x=1,y=a; while(b > 0){ if(b%2 == 1){ x=(x*y)%c; } y = (y*y)%c; b /= 2; } return x%c; } bool Miller(long long p,int iteration){ if(p<2){ return false; } if(p!=2 && p%2==0){ return false; } long long s=p-1; while(s%2==0){ s/=2; } for(int i=0;i<iteration;i++){ long long a=rand()%(p-1)+1,temp=s; long long mod=modulo(a,temp,p); while(temp!=p-1 && mod!=1 && mod!=p-1){ mod=mulmod(mod,mod,p); temp *= 2; } if(mod!=p-1 && temp%2==0){ return false; } } return true; } int main() { int t; long long m,n; cin>>t; while(t--) { cin>>m>>n; for(long long i=m;i<=n;i++) { if(Miller(i,6)) cout<<i<<endl; } cout<<endl; } }
Sunday, July 31, 2011
Miller Rabin Algorithm for Prime Generation
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment