C Program to Perform Fermat Primality Test

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.

1. `#include <stdio.h>`
2. `#include <stdlib.h>`
3. ` `
4. `#define ll long long`
5. `/*`
6. ` * modular exponentiation`
7. ` */ll modulo(ll base, ll exponent, ll mod) {`
8. `    ll x = 1;`
9. `    ll y = base;`
10. `    while (exponent > 0) {`
11. `        if (exponent % 2 == 1)`
12. `            x = (x * y) % mod;`
13. `        y = (y * y) % mod;`
14. `        exponent = exponent / 2;`
15. `    }`
16. `    return x % mod;`
17. `}`
18. ` `
19. `/*`
20. ` * Fermat's test for checking primality`
21. ` */`
22. `int Fermat(ll p, int iterations) {`
23. `    int i;`
24. `    if (p == 1) {`
25. `        return 0;`
26. `    }`
27. `    for (i = 0; i < iterations; i++) {`
28. `        ll a = rand() % (p - 1) + 1;`
29. `        if (modulo(a, p - 1, p) != 1) {`
30. `            return 0;`
31. `        }`
32. `    }`
33. `    return 1;`
34. `}`
35. `/*`
36. ` * Main`
37. ` */`
38. `int main() {`
39. `    int iteration = 50;`
40. `    ll num;`
41. `    printf("Enter integer to test primality: ");`
42. `    scanf("%lld", &num);`
43. `    if (Fermat(num, iteration) == 1)`
44. `        printf("%lld is prime ", num);`
45. `    else`
46. `        printf("%lld is not prime ", num);`
47. `    return 0;`
48. `}`

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.