The major approach to finding the prime number is running the loop from 2 to n and check whether it divides the number or not. The complexity of that solution is O(n).

In this article, We will be discussing how to find the prime number in O(sqrt(n))complexity.

lets us take the equation a*b = n On observing, we can consider the value of a as sqrt(n) and the value of b as sqrt(n).

If the value of a is less than or equal to sqrt(n), then the value of b is greater than or equal to sqrt(n).

We will not be using the math library in c++ to find sqrt(n) because it gives unexpected value. instead of using i<sqrt(n), we will be using i*i<n

bool isPrime(int n)
{
    if(n==1)
    {
        return false;
    }
    for(int i=2;i*i<n;i++)
    {
        if(n%i == 0)
        {
            return false;
        }
    }
    return true;
}