This C++ Program demonstrates the implementation of Fermat Primality Test.

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

`/*`

`* C++ Program to Implement Fermat Primality Test`

`*/`

`#include <cstring>`

`#include <iostream>`

`#include <cstdlib>`

`#define ll long long`

using namespace std;

`/*`

`* 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`

`*/`

bool Fermat(ll p, int iterations)

`{`

if (p == 1)

`{`

return false;

`}`

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

`{`

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

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

`{`

return false;

`}`

`}`

return true;

`}`

`/*`

`* Main`

`*/`

int main()

`{`

int iteration = 50;

`ll num;`

cout<<"Enter integer to test primality: ";

cin>>num;

if (Fermat(num, iteration))

cout<<num<<" is prime"<<endl;

`else`

cout<<num<<" is not prime"<<endl;

return 0;

`}`

$ g++ fermat_primality.cpp $ a.out Enter integer to test primality: 479001599 479001599 is prime ------------------ (program exited with code: 1) Press return to continue

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

If you wish to look at all C++ Programming examples, go to C++ Programs.