Primality Test

Given an integer N, we need to find whether N is prime or not.

A prime number is a natural number which has only two factors (1 and the number itself). If the number has any other factor, it is not a prime number.

To check if the given number N has any factor other than 1 and N, we need to check each integer between 2 to N1/2  (inclusive).

If any of these integers divides N, we say that N is not a prime number.

If there is no integer between 2 and N1/2 (inclusive) that divides N, then N is said to be a prime number.

Why to search only till N1/2 instead of N-1?

If A is a factor of N, then B=N/A is also a factor of N.

A * B = N  (A, B and N are natural numbers)

We observe that,

  • If A is less than N1/2, then B is greater than N1/2 and vise-versa.
  • If A = N1/2 then B = N1/2.

From the above observation we can say that,
For every integer A between 2 and N1/2 which is a factor of N, there will be a corresponding integer B between N1/2 to N-1 which is also a factor of N.

Similarly, for every integer A between N1/2 to N-1 which is a factor of N, there will be a corresponding integer B between 2 to N1/2 which is also a factor of N.

So, checking only the numbers from 2 to N1/2 is sufficient.

EXAMPLE 1:

  Screenshot 86

EXAMPLE 2:

  Screenshot 87

Time Complexity : O(N1/2)
Space Complexity : O(1)

CODE FOR PRIMALITY TEST:

#include<iostream>
#include<math.h>
using namespace std;
bool check_prime(int N) // function to check if N is prime or not
{
    int i;
    for(i=2;i<=sqrt(N);i++) // loop to check integers from 2 to squareroot(N)
    {
        if(N%i==0) // checking if any integer between 2 and squareroot(N) is a factor of N
        {
            return false; // if yes, N is not a prime number, returns false
        }
    }
    return true; // if there is no such factor, N is a prime number, returns true
}
int main()
{
    int N;
    bool b;
    cout << "Enter the value of N" << endl;
    cin >> N; // taking N as input
    b=check_prime(N); // calling function check_prime which returns true if N is prime, and false if N is not prime
    if(b==true)
    {
        cout << N << " is a prime number" << endl;
    }
    else
    {
        cout << N << " is not a prime number" << endl;
    }
    return 0;
}

 TESTCASE:

Enter the value of N
37
37 is a prime number