You are not logged in. Please login at www.codechef.com to post your questions!

×

Miller Rabin Deterministic Algorithm

 0 I wrote the following code for finding prime numbers between two given integers n,m Instead of the standard sieve method I tried using the Miller-Rabin test. http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test But the following code is giving a wrong answer in prime1, please help. #include #include #include #include #include #include #include #include #include using namespace std; #define inf 1000000007 #define mp make_pair #define pb push_back #define f(i,j) for(int i=0;i0;i--) #define fre(i,j) for(int i=j;i>=0;i--) //2 7 61 map prm; long long int t[3]={2,7,61}; long long int mod_pow(long long int a,long long int b,long long int n){ long long int res=1; while(b){ if(b%2){ res=(res*a)%n; } a=(a*a)%n; b/=2; } return res; } pair thed(long long int n){ long long int cnt=0; while(n%2==0){ n/=2; cnt++; } return mp(n,cnt); } int isprime(long long int n){ if(n==1){ return 0; } else if(n==2){ return 1; } else if(n==3){ return 1; } else if(n==5){ return 1; } else if(n==7){ return 1; } else if(n==61){ return 1; } else{ long long int a,x,d,flag; int s; pair ast=thed(n-1); d=ast.first; s=ast.second; f(i,3){a=t[i]; x=mod_pow(a,d,n); if(x==1 or x==n-1){ continue; } else{ flag=1; f(i,s-1){ x=(x*x)%n; if(x==1){ return 0; } if(x==n-1){ flag=0; break; } } if(flag){ return 0; } } } return 1; } } int main(){ int t; long long int n,m; cin>>t; while(t--){ cin>>m>>n; for(long long int i=m;i<=n;i++){ if(isprime(i)){ cout<

 0 Because it may be missing some prime numbers or test non-prime numbers as prime. You can check by producing primes by both sieve and millerrabin and compare the result. answered 21 Dec '13, 15:12 3★hatim009 464●2●11●22 accept rate: 8% I used the deterministic version of the test where we have to check only some testers for n<=1,000,000,000 having a=2,7,61, as stated in Wikipedia, (21 Dec '13, 15:19) How can it be missing some numbers if it is deterministic? I checked with codes of other users and using the diff command and it seems to give the correct answer. (21 Dec '13, 15:52)
 0 @epsilon_0 you can understand and try this The Algorithm is slower than Fermat’s Little primality test but is still preferred due to it’s high accuracy. Try out this problem on SPOJ/PON Here’s the python implementation – import random def exp(a,p,m): if (p==0): return 1 elif (p%2==1): return (aexp(a,p-1,m))%m x=exp(a,p/2,m) return (xx)%m def miller_rabin(p): if (p==2 or p==3):return 1 if (p%2==0):return 0 if (p<3):return 0 for i in range(10): #random 'a' a = random.randrange(2,p-2) s=p-1 while(s%2==0):s/=2 mod = exp(a,s,p) if (mod==1 or mod==p-1): continue flag=0 while(s!=(p-1)): mod = exp(a,s,p) if (mod==(p-1)): flag=1 break s*=2 if (flag==0): return 0 return 1  answered 11 Mar '17, 16:14 904●10 accept rate: 9%
 toggle preview community wiki:
Preview

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×69
×16

question asked: 21 Dec '13, 13:48

question was seen: 2,786 times

last updated: 11 Mar '17, 16:14