c - 我查找素数的代码不起作用。这里有什么问题？

Question

我试图找到最高 1000 的素数，但我只得到 2 和 3。

void main()
{
    int i = 1, j, n = 1000;

    while (n != 0)
    {
        j = 2;
        i++;
        if (i % j != 0)
        {
            j++;
        }

        if (i == j)
        {
            printf("%d\n", i);
            n--;
        }
    }
}

标签： c

Answer 1

你的代码有问题：

• 你应该#include <stdio.h>

• 的原型main不正确，它应该返回int。

• 您应该在循环外初始化j并以稍微不同的顺序运行测试。

• 该代码并非旨在查找最多 1000 的素数，而是查找前 1000 个素数。

这是一个更正的版本：

#include <stdio.h>

// print the first 1000 prime numbers
int main() {
    int i = 2, j = 2, n = 1000;

    while (n != 0) {
        if (i % j == 0) {
            if (i == j) {
                printf("%d\n", i);
                n--;
            }
            j = 2;
            i++;
        } else {
            j++;
        }
    }
    return 0;
}

但是请注意，您的算法令人困惑且效率低下：

• 您将真正应该表达为 2 个嵌套循环的内容组合在一个循环中。

• 你测试所有除数到i，而你可以在 时停止j * j > i，将时间复杂度从O(N ² )降低到O(N ^1.5 )。

• 您也可以在特殊情况下2仅测试奇数和除数，从而进一步减少除数的另一个因素。

这是一个替代方案：

#include <stdio.h>

// print the first 1000 prime numbers
int main() {
    int i, j, n = 1000;

    if (n > 0) {
        printf("%d\n", 2);
        n--;
    }

    i = 3;
    while (n > 0) {
        for (j = 3;; j += 2) {
            if (j * j > i) {
                printf("%d\n", i);
                n--;
                break;
            }
            if (i % j == 0)
                break;
        }
        i += 2;
    }
    return 0;
}