First prime number larger than given integer

Question

How can I test this C program for "efficiency"? The most interesting usage is that it returns negative output for large enough input, otherwise the behavior is about expected. Will you suggest how to improve the code, both the ui used in main that should be both efficient and preferably platform-indepedent and not use too much libraries for portability and optimization. I think the obvious improvement that I can make is recoding the int to unsigned int:

/*
 * NextPrime
 *
 * Return the first prime number larger than the integer
 * given as a parameter. The integer must be positive.
 */
#define PRIME_FALSE   0     /* Constant to help readability. */
#define PRIME_TRUE    1     /* Constant to help readability. */
#include <stdio.h>
#include <stdlib.h>
int nextprime(int inval) {
    int perhapsprime; /* Holds a tentative prime while we check it. */
    int testfactor; /* Holds various factors for which we test perhapsprime. */
    int found; /* Flag, false until we find a prime. */

    if (inval < 3) /* Initial sanity check of parameter. */
    {
        if (inval <= 0)
            return (1); /* Return 1 for zero or negative input. */
        if (inval == 1)
            return (2); /* Easy special case. */
        if (inval == 2)
            return (3); /* Easy special case. */
    } else {
        /* Testing an even number for primeness is pointless, since
         * all even numbers are divisible by 2. Therefore, we make sure
         * that perhapsprime is larger than the parameter, and odd. */
        perhapsprime = (inval + 1) | 1;
    }
    /* While prime not found, loop. */
    for (found = PRIME_FALSE; found != PRIME_TRUE; perhapsprime += 2) {
        /* Check factors from 3 up to perhapsprime/2. */
        for (testfactor = 3; testfactor <= (perhapsprime >> 1) + 1; testfactor
                += 1) {
            found = PRIME_TRUE; /* Assume we will find a prime. */
            if ((perhapsprime % testfactor) == 0) /* If testfactor divides perhapsprime... */
            {
                found = PRIME_FALSE; /* ...then, perhapsprime was non-prime. */
                goto check_next_prime;
                /* Break the inner loop, go test a new perhapsprime. */
            }
        }
        check_next_prime: ; /* This label is used to break the inner loop. */
        if (found == PRIME_TRUE) /* If the loop ended normally, we found a prime. */
        {

            return (perhapsprime); /* Return the prime we found. */
        }
    }

    return (perhapsprime); /* When the loop ends, perhapsprime is a real prime. */
}

int main(int argc, char *argv[]) {
    int intvar;
    if (sscanf(argv[1], "%i", &intvar) != 1) {
        printf("please use an integer parameter to compute the next prime\n");
    } else
        printf("%d => %d\n", intvar, nextprime(intvar));
    return 0;
}

Answer 1

Things you could improve

Efficiency

• As @rolfl stated, you want to use a Sieve of Eratosthenes (+1 to that answer).

  

• I can't see if you are doing this already, but you should be compiling with your compiler's highest optimization level. With GCC for example, this would be -O3.

Portability

• Keep in mind to adhere to the standards as closely as possible, because a system that supports C must adhere to the standards as well.

• If you want your program to be as portable as possible, take a look into the AutoTools suite for packaging your program. This is a bit extreme in your case, since you aren't using external libraries, and your program doesn't have a lot of system dependencies.

Standards

• You don't have to return 0 at the end of main(), just like you wouldn't bother putting return; at the end of a void-returning function. The C standard knows how frequently this is used, and lets you not bother.

  C99 & C11 §5.1.2.2(3)

  ...reaching the } that terminates the main() function returns a value of 0.

• Use the standard library <stdbool.h> instead of defining your own boolean values.

  #define PRIME_FALSE   0     /* Constant to help readability. */
  #define PRIME_TRUE    1     /* Constant to help readability. */
  

  It still helps with readability. And since it is part of the standard in C, systems are guaranteed to have it if they support C.

Syntax/Styling

• Don't use goto.

  

  Yes, there are some rare situations where you may find it necessary to use it. This is not one of them. A simple break; will suffice in it's place, since you are only breaking out of the inner loop.

• Right now you are using a somewhat odd way to test if you have an integer input into the command line arguments.

  if (sscanf(argv[1], "%i", &intvar) != 1)
  

  Use argc to test the number of arguments input into the program instead, and isdigit to test if the input contains numbers.

  if (argc != 2 || !isdigit(**(argv+1))) printf("Please use an integer parameter to compute the next prime.\n");
  

  Then convert that input into an integer.

  int intvar = atoi(*(argv+1));
  

  Note that the order I put it in is important. We want to test argc first, so we put it first in the test conditional. If that fails, the second part on the other side of the || isn't even evaluated, and the statements following the conditional are executed. If we switched those tests around, undefined behavior could occur if we didn't enter in a command line argument.

• Use puts() instead of printf() when you aren't formatting your strings. This allows you to not worry about the newline (\n) character at the end of your printed out strings.

  puts("Please use an integer parameter to compute the next prime.");
  

• You don't modify the value of intval within your nextprime() function, therefore the parameter should be declared constant.

  int nextprime(const int inval)
  

• You can reduce down one of your test conditionals.

  if (inval == 1)
      return (2); /* Easy special case. */
  if (inval == 2)
      return (3); /* Easy special case. */
  

  if (inval == 1 || inval == 2) return (inval + 1); /* Easy special case. */
  

Answer 2

Let's review the context of this function.

If this function will be called often with a wide range of inputs, then it makes sense to pre-compute a bunch of prime numbers and then just find where the input value is in amongst the pre-coumputed set. When pre-computing the primes the most common way is through using a Sieve of Eratosthenes (wikipedia).

Your function is not a Sieve, and, as a result, will only be efficient for calculating just one prime number.... This is not actually a criticism, it is just a contextualization.

Now, about your code:

Simplified IF statement

Your statement is:

if (inval < 3) /* Initial sanity check of parameter. */
{
    if (inval <= 0)
        return (1); /* Return 1 for zero or negative input. */
    if (inval == 1)
        return (2); /* Easy special case. */
    if (inval == 2)
        return (3); /* Easy special case. */
} else {
    /* Testing an even number for primeness is pointless, since
     * all even numbers are divisible by 2. Therefore, we make sure
     * that perhapsprime is larger than the parameter, and odd. */
    perhapsprime = (inval + 1) | 1;
}

This has a few 'features' I don't like:

• the 'true' side of the block has the fall-though if (intval == ?) conditions. The last condition will always be true, so why test it?
• 1 is not a prime number. The first prime is 2.
• The 'true' side of the main if will always return, so there is no need for the else block.

Bottom line is I would simplify this condition to:

if (inval < 2) /* Initial sanity check of parameter. */
{
    return (2); /* Easy special case. */
}

/* Testing an even number for primeness is pointless, since
 * all even numbers are divisible by 2. Therefore, we make sure
 * that perhapsprime is larger than the parameter, and odd. */
perhapsprime = (inval + 1) | 1;

Simplified Loops

Exit conditions:

your code has a relatively simple 'big' for loop:

for (found = PRIME_FALSE; found != PRIME_TRUE; perhapsprime += 2) {

...but, inside that loop, just before it iterates, you double-check the found condition and return if it is PRIME_TRUE.... Why the double-check? The double-check makes the outside-the-loop return statement unreachable.

The awkwardness of your code suggests you are using the wrong structures. I would recommend a different system entirely.... this problem space is well-suited for a do-while loop with a 'special' initializer. Consider the following loop:

// set up 'special' initializer (it will be re-incremented in the loop)
perhapsprime -= 2;
do {
    perhapsprime += 2;

    // check if perhapsprime is true now
    ....

} while (found != PRIME_TRUE);
return perhapsprime;

Now, in the interest of readability, I would actually extract the entire content of that loop to another function, say is_prime(int perhapsprime), then your entire nextprime function will become:

int nextprime(int inval) {
    int perhapsprime; /* Holds a tentative prime while we check it. */
    int found;

    if (inval < 2) /* Initial sanity check of parameter. */
    {
        return (2); /* Easy special case. */
    }

    /* Testing an even number for primeness is pointless, since
     * all even numbers are divisible by 2. Therefore, we make sure
     * that perhapsprime is larger than the parameter, and odd. */
    perhapsprime = (inval + 1) | 1;

    perhapsprime -= 2; /* pre-set the loop variable */
    do {
        perhapsprime += 2;
        found = is_prime(perhapsprime);
    } while (found != PRIME_TRUE);
    return perhapsprime;
}

BUT: now that the function-extraction has happened, it can be replaced by a simple while loop instead of the do-while:

    /* Testing an even number for primeness is pointless, since
     * all even numbers are divisible by 2. Therefore, we make sure
     * that perhapsprime is larger than the parameter, and odd. */
    perhapsprime = (inval + 1) | 1;

    while (is_prime(perhapsprime) != PRIME_TRUE) {
        perhapsprime += 2;
    }
    return perhapsprime;

is_prime

OK, now we have to move the inner-guts of your loop to a is_prime function. For the most part, this is a copy-paste exercise....

int is_prime(int perhapsprime) {

    int limit;
    int testfactor;

    limit = (perhapsprime >> 1) + 1; /** SEE NOTES!!! */

    for (testfactor = 3; testfactor <= limit; ++testfactor) {
        if ((perhapsprime % testfactor) == 0) /* If testfactor divides perhapsprime... */
        {
            return PRIME_FALSE; /* ...then, perhapsprime was non-prime. */
        }
    }

    return PRIME_TRUE;
}

Special notes here:

• Using limit = (perhapsprime >> 1) + 1 may improve performance by only computing the limit one time. My C experience is not enough to tell you that for sure. It makes the code more readable anyway.
• using limit = (perhapsprime >> 1) + 1 is not the best limit. It should be sqrt(perhapsprime) to get the true limit.
• I have used ++testfactor in the loop incrementor because it is best-practice to do a pre-inrement rather than a += 1.

Conclusion

Hopefully this will give you a few ideas, and show that the for-loop is not necessarily the best, or only loop structure.

Edit: I have put this all together in an ideone.