WAP to Calculate the next Smallest Prime Number From Given Number Efficiently

Given a number n, compute the smallest prime that is bigger than n. For example, n=8, then the smallest prime that bigger than 8 is 11. n=23 o/p is 29 & so on

#include

int power(int x, int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}


double sqrt(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX) {
lastX = xn;
xn = (xn + s/xn) / 2.0;
}

return xn;

}
bool is_prime(int x)
{
if(x <= 1)
return false;
int s = (int) sqrt(x);
for(int i = 2; i <= s; i++)
if(x%i == 0)
return false;
return true;
}

int next_prime(int n)
{
int i=n+1;


/*The largest known Mersenne prime (243,112,609 − 1) is also the largest known prime
number,else // no such prime exist explain above
int pow=power(2,243112609)−1;
if(n>pow)
return 0; this line wont execute overflow*/

while(true)
{

if(is_prime(i))
break;
i++;

}
return i;
}
int main()
{
printf( " %d ", next_prime(23));
return 0;

}


TC of isprime is O(sqrt(n))
TC of sqrt is log(n)
TC of pow function is O(logn)
TC of next prime O(k*sqrt(n) where k is number of iteration used to find next smallest prime so k is constant & so overall time complexity of this algo is O(sqrt(n))

TC O(sqrt(n))
SC O(1)
Run Here https://ideone.com/5ViQe

Feel Free to Comment or Optimize the solution or if any issue with time complexity