第一个素数大于给定的整数

/*
 * 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;
}

#1 楼

您可以改善的事情

效率



如@rolfl所述，您想使用Eratosthenes筛（该答案为+1）。



我看不到您是否已经在执行此操作，但是您应该使用编译器的最高优化级别进行编译。以GCC为例，这将是-O3。

可移植性


请记住要尽可能严格地遵循标准，因为支持C的系统还必须遵守标准。
如果希望程序具有尽可能好的可移植性，请查看用于打包程序的AutoTools套件。在您的情况下，这有点极端，因为您没有使用外部库，并且您的程序没有很多系统依赖性。

标准



您不必在0的末尾返回main()，就像您不会费心将return;放在void -returning函数的末尾一样。 C标准知道它的使用频率，并且让您不必打扰。


C99和C11§5.1.2.2（3）

...到达终止}函数的main()返回0的值。



使用标准库<stdbool.h>而不是定义自己的布尔值。

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

它仍然有助于提高可读性。并且由于它是C语言标准的一部分，因此，如果系统支持C语言，则可以保证系统具有此语法。 br />不要使用goto。



是的，在某些罕见的情况下，您可能会发现有必要使用它。这不是其中的一个。一个简单的break;就足够了，因为您只是在打破内循环。


现在，您正在使用一种有点奇怪的方法来测试是否有整数输入命令行参数。

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

请改用argc测试输入到程序中的参数数量，并使用isdigit测试输入是否包含数字。
然后将输入转换为整数。

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

请注意，输入的顺序很重要。我们要先测试argc，因此我们将其放在有条件的测试中。如果失败，则甚至不会评估||另一侧的第二部分，并执行条件语句之后的语句。如果我们切换这些测试，那么如果不输入命令行参数，可能会发生不确定的行为。


在不格式化字符串时，请使用puts()而不是printf()。这使您不必担心打印出的字符串末尾的换行符（\n）。

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

您无需修改​​值intval函数中的nextprime()的整数，因此应将参数声明为常量。

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

您可以减少其中一个测试条件。

int nextprime(const int inval)

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

评论

---

\ $ \ begingroup \ $
“ *（argv + 1）”为什么不是argv [1]？
\ $ \ endgroup \ $
–尼古拉斯B.
2014年3月31日下午3:17

---

\ $ \ begingroup \ $
@NiklasB。没关系。您可以用任何一种方式编写它。那就是我选择的方式。
\ $ \ endgroup \ $
–syb0rg
2014年3月31日在3:23

---

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

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;

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

// 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;

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

    /* 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;

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