你是质数吗

多年来我一直对寻找更好的素数识别器的问题感兴趣。我意识到这是一个巨大的学术研究领域——我对此的兴趣实际上只是为了好玩。这是我在 C 语言中第一次尝试可能的解决方案（如下）。

我的问题是，你能提出改进建议吗（没有引用网上的其他参考资料，我正在寻找实际的 C 代码）？我试图从中得到的是更好地理解确定此类解决方案的性能复杂性。

我认为这个解决方案的复杂度是 O(n^2) 的结论正确吗？

#include <stdio.h>
#include <math.h>

/* isprime                                                           */
/* Test if each number in the list from stdin is prime.              */
/* Output will only print the prime numbers in the list.             */

int main(int argc, char* argv[]) {

    int returnValue = 0;
    int i;
    int ceiling;
    int input = 0;
    int factorFound = 0;

    while (scanf("%d", &input) != EOF) {

        ceiling = (int)sqrt(input);
        if (input == 1) {
            factorFound = 1;
        }

        for (i = 2; i <= ceiling; i++) {
            if (input % i == 0) {
                factorFound = 1;
            } 
        }

        if (factorFound == 0) {
            printf("%d\n", input);
        }

        factorFound = 0;    
    } 

    return returnValue;
}

   for (i = 2; i <= ceiling; i++) {
        if (input % i == 0) {
            factorFound = 1;
            break;
        } 
    }

这是第一个改进，并且仍然保持在“相同”算法的范围内。根本不需要任何数学知识就能看到这一点。

除此之外，一旦你看到了input不能被2整除，则无需检查4、6、8等。如果有偶数被整除input，那么 2 肯定会有，因为它能整除所有偶数。

如果你想稍微跳出算法一步，你可以使用像下面这样的循环：谢尔顿·L·库珀 https://stackoverflow.com/questions/3793697/are-you-a-prime-number/3793790#3793790在他的回答中提供了。 （这比让他从评论中纠正我的代码更容易，尽管他的努力非常值得赞赏）

这利用了除 2 和 3 之外的每个素数都具有以下形式的事实n*6 + 1 or n*6 - 1对于某个正整数n。要看到这一点，只需注意如果m = n*6 + 2 or m = n*6 + 4, then n能被 2 整除。如果m = n*6 + 3那么它可以被 3 整除。

事实上，我们可以更进一步。如果p1, p2, .., pk是第一个k素数，那么所有与其乘积互质的整数都标记出所有剩余素数必须适合的“槽”。

看到这个，只需让k#是所有素数的乘积pk。那么如果gcd(k#, m) = g, g划分n*k# + m所以这个总和是微不足道的复合如果g != 1。所以如果你想迭代5# = 30，那么你的互质整数是 1, 7, 11, 13, 17, 19, 23 和 29。

从技术上讲，我没有证明我最后的主张。并没有更困难

if g = gcd(k#, m)，那么对于任意整数，n, g划分n*k# + m因为它划分k#所以它也必须除n*k#。但它划分m同样，它必须除以总和。上面我只是证明了n = 1。我的错。

另外，我应该指出，这些都没有改变算法的基本复杂性，它仍然是 O(n^1/2)。它所做的只是彻底地减少用于计算实际预期运行时间的系数。