To Find Number Is Prime Or Not At Very Less Complexity (O(sqrt(n)))

Prime numbers are the numbers which has only 2 factors i.e divisble by 1 and the number itself


Function:

bool isPrime(int n)
{
if(n<=1)   // if number is less than  number is not prime
  return false;
if(n<=2)     // if number is less than 2 than it prime because it is divisible by 2 and 1
  return true;
if(n%2==0||n%3==0)   // if the number is divided by 2 or 3 than it is not prime
{
return false;
}
for(int i=5;i*i<=n;i=i+6) 
     // check for 5 and than 11 than 17 which is all prime number  
   {
    if(n%i==0||n%(i+2)==0) 
   // check for 5 than 7 than 11 than 13 and so on
       return false;
   }
return true;
}