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 <code>O(n)</code>.
In this article, We will be discussing how to find the prime number in <code>O(sqrt(n))</code>complexity.
lets us take the equation <code>a*b = n</code>
On observing, we can consider the value of <code>a</code> as sqrt(n) and the value of <code>b</code> as <code>sqrt(n)</code>. 
If the value of <code>a</code> is less than or equal to <code>sqrt(n)</code>, then the value of <code>b</code> is greater than or equal to <code>sqrt(n)</code>. 
We will not be using the math library in c++ to find sqrt(n) because it gives unexpected value.
instead of using <code>i&lt;sqrt(n)</code>, we will be using <code>i*i&lt;n</code>
<pre><code>bool isPrime(int n)
{
 if(n==1)
 {
 return false;
 }
 for(int i=2;i*i&lt;n;i++)
 {
 if(n%i == 0)
 {
 return false;
 }
 }
 return true;
}
</code></pre>

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;
}
```

Finding the Prime number in sqrt(n) Complexity