Primality C++ Test Using a Basic Concept of Number Theory

 Primality testing is some sort of exciting stuff for a beginner in coding. There are various techniques for doing this. Following code is written by me that used the following fact that -: "N is a composite number if it has at least one non-trivial divisor d, such that d is less than or equal to sqrt(N)". 

Proof of the fact is simple and can be proved using contradiction(Hint -; N is composite. What if all the non-trivial divisors are greater than sqrt(N)? ).

Direct link -: http://cpp.sh/7sng3

// To detect whether a number is prime or not.

// Written by Sushant

#include <iostream>

#include<cmath>

using namespace std;

int main()

{

int p,q,i(0),d(0);

cout<<"Enter the number -: \n";

cin>>p; // enter the prime

q=int(sqrt(p)); // storing the integer part of square root

                  for(i=2; i <= q;i++)

                           {

                                // using the fact that if x is a composite number then it must have a non-trivial divisor less than or equal to sqrt(x)

                                

                                if (p%i == 0) 

                                        {

                                            d++;

                                            i=q+1; // to stop the for loop

                                        }

                            }

                            

                            // Now the final result

                  if(d==0)

                           { 

                               if(p==1)

                                    cout<<"is not prime";

                               else

                                    cout<<"is prime";

                           }

                  else

                            cout<<"is not prime";

 return 0;

  

}