This is a C Program to test whether a number is prime or not. The Fermat primality test is a probabilistic test to determine if a number is probable prime.

Here is source code of the C Program to Perform Fermat Primality Test. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include <stdio.h>`

`#include <stdlib.h>`

`#define ll long long`

`/*`

`* modular exponentiation`

*/ll modulo(ll base, ll exponent, ll mod) {

ll x = 1;

ll y = base;

while (exponent > 0) {

if (exponent % 2 == 1)

x = (x * y) % mod;

y = (y * y) % mod;

exponent = exponent / 2;

`}`

return x % mod;

`}`

`/*`

`* Fermat's test for checking primality`

`*/`

int Fermat(ll p, int iterations) {

int i;

if (p == 1) {

return 0;

`}`

for (i = 0; i < iterations; i++) {

ll a = rand() % (p - 1) + 1;

if (modulo(a, p - 1, p) != 1) {

return 0;

`}`

`}`

return 1;

`}`

`/*`

`* Main`

`*/`

int main() {

int iteration = 50;

`ll num;`

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

scanf("%lld", &num);

if (Fermat(num, iteration) == 1)

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

`else`

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

return 0;

`}`

Output:

$ gcc FermatPrimeTest.c $ ./a.out Enter integer to test primality: 45 45 is not prime Enter integer to test primality: 97 97 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.