This C program implements the Rabin-Miller Primality Test to check if a given number is Prime. The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test.

Here is the source code of the C program to check if a given number is prime or not. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include <stdio.h>`

`#include <string.h>`

`#include <stdlib.h>`

`/*`

`* calculates (a * b) % c taking into account that a * b might overflow`

`*/`

long long mulmod(long long a, long long b, long long mod)

`{`

long long x = 0,y = a % mod;

while (b > 0)

`{`

if (b % 2 == 1)

`{`

x = (x + y) % mod;

`}`

y = (y * 2) % mod;

b /= 2;

`}`

return x % mod;

`}`

`/*`

`* modular exponentiation`

`*/`

long long modulo(long long base, long long exponent, long long mod)

`{`

long long x = 1;

long long y = base;

while (exponent > 0)

`{`

if (exponent % 2 == 1)

x = (x * y) % mod;

y = (y * y) % mod;

exponent = exponent / 2;

`}`

return x % mod;

`}`

`/*`

`* Miller-Rabin Primality test, iteration signifies the accuracy`

`*/`

int Miller(long long p,int iteration)

`{`

int i;

long long s;

if (p < 2)

`{`

return 0;

`}`

if (p != 2 && p % 2==0)

`{`

return 0;

`}`

s = p - 1;

while (s % 2 == 0)

`{`

s /= 2;

`}`

for (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 0;

`}`

`}`

return 1;

`}`

`//Main`

int main()

`{`

int iteration = 5;

long long num;

printf("Enter integer to test primality: ");

scanf("%lld", &num);

if ( Miller( num, iteration))

printf("\n%lld is prime\n", num);

`else`

printf("\n%lld is not prime\n", num);

return 0;

`}`

$ gcc bubblesort.c -o bubblesort $ ./bubblesort Enter integer to test Primality: 89 89 is prime

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

Here’s the list of Best Reference Books in C Programming, Data Structures and Algorithms.