text: Primality Test | Set 3 ( Millerâ €“ Rabin ) | C ++ program Miller - Rabin primality test ; Utility function to do modular exponentiation . It returns ( x ^ y ) % p ; Initialize result ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 ; y = y / 2 ; This function is called for all k trials . It returns false if n is composite and returns true if n is probably prime . d is an odd number such that d * 2 < sup > r < / sup > = n - 1 for some r >= 1 ; Pick a random number in [ 2. . n - 2 ] Corner cases make sure that n > 4 ; Compute a ^ d % n ; Keep squaring x while one of the following doesn 't  happen  (i) d does not reach n-1  (ii) (x^2) % n is not 1  (iii) (x^2) % n is not n-1 ; Return composite ; It returns false if n is composite and returns true if n is probably prime . k is an input parameter that determines accuracy level . Higher value of k indicates more accuracy . ; Corner cases ; Find r such that n = 2 ^ d * r + 1 for some r >= 1 ; Iterate given nber of ' k ' times ; Driver program
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int power ( int x , unsigned int y , int p ) { int res = 1 ; x = x % p ; while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } bool miillerTest ( int d , int n ) { int a = 2 + rand ( ) % ( n - 4 ) ; int x = power ( a , d , n ) ; if ( x == 1 x == n - 1 ) return true ; while ( d != n - 1 ) { x = ( x * x ) % n ; d *= 2 ; if ( x == 1 ) return false ; if ( x == n - 1 ) return true ; } return false ; } bool isPrime ( int n , int k ) { if ( n <= 1 n == 4 ) return false ; if ( n <= 3 ) return true ; int d = n - 1 ; while ( d % 2 == 0 ) d /= 2 ; for ( int i = 0 ; i < k ; i ++ ) if ( ! miillerTest ( d , n ) ) return false ; return true ; } int main ( ) { int k = 4 ; cout << " All ▁ primes ▁ smaller ▁ than ▁ 100 : ▁ STRNEWLINE " ; for ( int n = 1 ; n < 100 ; n ++ ) if ( isPrime ( n , k ) ) cout << n << " ▁ " ; return 0 ; }