HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Find smallest prime number greater than given n

Submitted by: @import:stackexchange-codereview··
0
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?

#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.