Fermat Primality Test in C++

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.

« Prev - Sudoku Problem using BackTracking in C++

» Next - C++ Program to Count Inversions in an Array

Related Posts:

Recommended Articles: