在C中显示素数为2-10,000

Question

我正在努力解决这个(可选的)问题，我的教授建议我尝试一下。基本上，我的任务是编写一个程序，用我自己的用户定义的函数来确定质数，显示2-10,000之间的所有素数整数。这听起来很简单，但我在调试程序时遇到了很大的困难。由于某些原因，我的代码在结束前只显示2和3。

#include<stdio.h>
//function declaration
int prime(int);
//main body
int main(void)
{
    int x=2, y;
    for (x=2;x<=30;x++)
    {
        y=prime(x);
        if (y!=0)
            printf("%d\n", x);
    }
    getchar();
    return(0);
}
//function definition
int prime(int x)
{
    int y;
    for (y=2; y<=(int)sqrt(x); ++y)
    {
        if (x%y==0)
           return 0;
    }
    if (y==(int)sqrt(x))
       return 1;
}

如果x是素数，则不返回1，我的素数检查函数似乎返回一个随机的大数(2686xxx)，但这不应该是一个问题，因为所有素数都返回0。如果我做了这样的事情：

if (y==0)
    printf("%d\n", x);

我看到了所有非素数的列表。如果我做了这样的事情：

printf("%d    %d\n", x, y);

我看到了2-10,000的所有整数的列表以及我的素数检查函数的结果(非素数为0，素数为2686xxx )。

为什么相反的(y!=0)不显示素数列表？是什么导致我的代码在只显示2和3之后停止呢？为什么我的素数函数返回一个奇怪的整数而不是1？最后，我仍然是一个初学者，但是我怎样才能写出更好的代码呢？我不认为我违反了任何标准的公认的实践，但我如何才能使我的代码更干净或高效？

提前感谢您的帮助！

Answer 1

如果是y==(int)sqrt(x)，则循环继续。所以当它结束时，它们是不平等的。你想要的是：

if (y>=(int)sqrt(x))
   return 1;

但这根本不需要。只要return 1;就够了。如果数字不是素数，你已经返回了零。

如果您只想要一个返回语句：

int prime(int x)
{
    bool isPrime = true;
    int y;
    for (y=2; y<=(int)sqrt(x); ++y)
    {
        if (x%y==0)
        {
            isPrime = false;
            break;
        }
    }
    return isPrime;
}

Answer 2

在素数函数的末尾，只返回1，如果不是素数，它会在前面返回0。对吗？

实际上，您已经创建了一个函数，它有时根本不返回任何内容。这意味着它返回在寄存器中的任何随机值。

Answer 3

您可以使用eratosthenes中的S喜阶或atkin的sieve标记数组中的所有素数，然后显示素数。它将节省时间，尽管它会带来一些空间复杂性。

例如，如果你想显示素数从1到10

左1。它不是质数。它既不是质数，也不是合成物。

所以从2开始。

假设这个大小为10的数组=2 3 4 5 6 7 8 9 10

如果一个元素没有高亮显示它的所有倍数。

为2突出其倍数4 6 8 10

==> 2 3 4 5 6 7 8 9 10

对于3人，做同样的事情

==> 2 3 4 5 6 7 8 9 10E 217

然后对其余的数字做它，即5和10 (在这里，7没有倍数)

最后，打印非突出显示的元素。2,3,5,7

对任何其他范围重复此过程。