Introduction:
Mohammed and Ali were two friends who lived in Nazak. Recently they have learned the difference between prime numbers and composite numbers in their school. They have taught how to check if a number is prime or not in a naive way. The method says we must iterate through 2 to N/2 and check whether ‘N’ is divisible by at least one of these numbers. If yes, then it is a composite number. Else, if it is divisible by none of them, then it is a prime number.
Here ‘N’ is the given number upon which the primality test needs to be conducted. Given a large number, this would consume a lot of time. They wondered whether there exists a better way to do the primality test. After a lot of research, they found out that Fermat’s Primality Test can help them in the task.
In this blog, we will discuss the idea behind Fermat’s primality test as well as its implementation in C++. But before that, let us first see the naive approach of the primality test.
Naive Primality Test
Given a number of ‘N’, we need to check if it is a prime or not. To solve this problem, one can think of a naive method of iterating through 2 to N/2 and check if any of them divides ‘N’. If yes, it is not prime. Else it is a prime number.
The C++ implementation of the above idea is provided below:
Program
#include <bits/stdc++.h>

Input:
Enter the number to check its primality: 83 
Output:
No, 83 is not a prime number. 
Time Complexity
O(N), where ‘N’ is the given number.
It is because we are looping from 2 to N/2.
Space Complexity:
O(1).
As we are not using any extra space.
Also see, Euclid GCD Algorithm
Optimized Approach
Now let us discuss a better approach. It is not required to iterate to N/2. We can just iterate from two till SquareRoot(N). It is because the factor of a number occurs in pairs. So, if X is a factor of N, then N / X is also a factor of N. Therefore if we iterate from 2 till SquareRoot(N), all the factors will be covered.
Program
#include <bits/stdc++.h>

Input:
Enter the number to check its primality: 101 
Output:
Yes, 101 is a prime number. 
Time Complexity
O(sqrt(N)), where ‘N’ is the given number.
It is because we are looping from 2 to square root(N).
Space Complexity:
O(1).
As we are not using any extra space.
Now let us discuss Fermat’s primality test. This method is probabilistic and is based on Fermat’s Little Theorem.