2

我正在努力解决我的教授建议我尝试的这个（可选）问题。基本上，我的任务是编写一个程序，使用我自己的用户定义函数来显示从 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？最后，我仍然是一个初学者，但我如何才能写出更好的代码呢？我认为我没有违反任何公认的标准做法，但我怎样才能使我的代码更干净或更高效？

在此先感谢您的帮助！

4

5 回答 5

3

如果.你的循环继续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;
}
于 2013-11-08T08:06:58.990 回答
2

不要使用 sqrt() 函数。在数学中，如果你有'x = sqrt(y)'。如果你把两边都平方，你会得到类似'x * x = y'的东西。c 中的这个表达式比 sqrt 函数快得多。因此，而不是这样做：

y <= (int)sqrt(x)

你有没有循环保护是这样的：

y * y <= x

这是您的问题的运行示例：

素数 2 -> 10000

于 2013-11-08T10:12:34.807 回答
1

在你的素数函数结束时只返回 1。如果它不是素数，它会更早地返回 0。正确的？

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

于 2013-11-08T08:06:51.400 回答
0

您可以使用 sieve of eratosthenes 或 sieve of atkin 标记数组中的所有素数，然后显示素数。尽管会产生一些空间复杂性，但它会节省时间。

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

离开 1。它不是素数。它既不是素数也不是合数。

所以从2开始。

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

从 2 开始遍历。如果一个元素未突出显示，则突出显示其所有倍数。

即 2 突出其倍数 4 6 8 10

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

对于 3 做同样的事情

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

然后对其余的编号执行此操作，即 5 和 10（这里 7 没有多个）

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

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

于 2013-11-08T17:37:36.573 回答
0

由于您对编写素数的计算机程序感兴趣，也许您想把这篇论文变成一个计算机程序。它处理素数，类似于您试图在 C 中创建的筛子。

https://graveticpropulsion.files.wordpress.com/2015/04/prime-number-theory.pdf

我不确定它是更快还是更少的内存密集型，但我很好奇自己在它变得对计算机来说过于密集之前可以找到多高的质数。

于 2016-02-23T21:50:33.693 回答