# Miller Rabin Deterministic Algorithm

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

``````#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<numeric>
#include<stack>
#include<set>
#include<map>

using namespace std;

#define inf 1000000007
#define mp make_pair
#define pb push_back
#define f(i,j) for(int i=0;i<j;i++)
#define fe(i,j) for(int i=0;i<=j;i++)
#define fr(i,j) for(int i=j;i>0;i--)
#define fre(i,j) for(int i=j;i>=0;i--)

//2 7 61

map<long long int,long long int> 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<long long int,long long int> 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<long long int,long long int> 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<<i<<endl;
}
}
cout<<endl;
}
}
``````

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.

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,

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.

@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 (a*exp(a,p-1,m))%m
x=exp(a,p/2,m)
return (x*x)%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```
//