patterncMinor
Find smallest prime number greater than given n
Viewed 0 times
smallestnumbergreaterthanfindprimegiven
Problem
I need to write a program which will find a prime number, greater than the given n.
Can it be done simpler?
Can it be done simpler?
#include
int isPrime(int n)
{
int i,j=0;
for(i=1; i 2)
return 0;
}
int fun(unsigned int n)
{
int i=n+1;
while(1)
{
if(isPrime(i))
break;
i++;
}
return i;
}
int main(int argc, char **argv)
{
printf("%d\n", fun(19));
return 0;
}Solution
You can implement function
isPrime to test primality in a little more efficient manner:int isPrime(int n) // assuming n > 1
{
int i,root;
if (n%2 == 0 || n%3 == 0)
return 0;
root = (int)sqrt(n);
for (i=5; i<=root; i+=6)
{
if (n%i == 0)
return 0;
}
for (i=7; i<=root; i+=6)
{
if (n%i == 0)
return 0;
}
return 1;
}Code Snippets
int isPrime(int n) // assuming n > 1
{
int i,root;
if (n%2 == 0 || n%3 == 0)
return 0;
root = (int)sqrt(n);
for (i=5; i<=root; i+=6)
{
if (n%i == 0)
return 0;
}
for (i=7; i<=root; i+=6)
{
if (n%i == 0)
return 0;
}
return 1;
}Context
StackExchange Code Review Q#71212, answer score: 6
Revisions (0)
No revisions yet.