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

×

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

But the following code is giving a wrong answer in prime1, please help.

#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;
  }
}

asked 21 Dec '13, 13:48

epsilon_0's gravatar image

4★epsilon_0
4527
accept rate: 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.

link

answered 21 Dec '13, 15:12

hatim009's gravatar image

3★hatim009
46421122
accept rate: 8%

edited 21 Dec '13, 15:21

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) epsilon_04★

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) epsilon_04★

@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
link

answered 11 Mar '17, 16:14

adhish_kapoor's gravatar image

3★adhish_kapoor
90410
accept rate: 9%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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