关于“C”中的素数生成- 我的代码有什么问题吗？ -

Question

我是一名非正规计算机专业三年级学生，我刚刚意识到我必须开始编码。

我以较低的成绩通过了编码课程，因此我在编码和编程方面没有良好的背景。

我正在尝试编写一个代码来生成给定上限和下限之间的素数。对C不太了解，强迫我写一个粗略的代码然后再过一遍来解决。我可以轻松地设置预期功能的逻辑，但我可能通过几种不同的方式创建了错误的算法。

在这里我分享我的最后一个代码，我打算计算当一个数字给出余数 Zero 时，它应该是 self 和 1 ，这样 count==2;我的实现和解决方案生成方式有什么问题？我希望你能让我对编程世界产生兴趣，我找不到足够的动力和勇气去深入编程。

包含 Stdio 和 Math.h

int primegen(int down,int up)
{   
    int divisor,candidate,count=0,k;

    for(candidate=down;candidate<=up;candidate++)
    {
        for(divisor=1;divisor<=candidate;divisor++)
        {
            k=(candidate%divisor);
        }
        if (k==0) count++;
        if(count==2)
        {
            printf("%d\n", candidate);
            count=0;
        }
        else
        {
            continue;
        }
    }
}

int main()
{
    primegen(3,15);
    return 0;
}

Answer 1

您在 candidate%divisor 测试中包含 1 和 candidate，这两者都将始终返回 0，因此您测试的每个数字都将显示为素数。

而不是这样做：

for(divisor=1;divisor<=candidate;divisor++)

执行此操作：

for(divisor=2;divisor<candidate;divisor++)

update

您的代码有太多问题无法列出，但无论如何，这里有几个：

• for 循环外部检查 candidate%divisor 的结果
• 您正在通过 当你检查k时，k总是candidate%candidate，或者0
• 你只检查一次k，之后除数循环
• 在循环结束时不会继续，这就是默认情况下发生的情况。

看，这里是一些最简单的实现的伪代码。尝试找出您的代码与此的偏差：

for candidate = down to up
  // assume the candidate is primt
  prime = true

  // check all divisors from 2 to the candidate - 1, inclusive
  for divisor = 2 to candidate - 1
    if candidate % divisor == 0
      // divisor is a factor of candidate
      // candidate isn't prime, so we can stop checking
      prime = false
      break
    end if
  next divisor

  // if prime is still true, we successfully tested every number from 2..candidate
  // and found no factors
  if prime
    print "candidate {candidate} is prime!"
  end if
next candidate

Answer 2

• 在内部循环中，您计算​​所有除数的 candidate%divisor ，但只有在循环完成后，您才检查 count 是否应该增加。因此，对于检查的最后一个除数，每个候选者只需增加一次。
• 此外，您也不会重置外循环中每个候选者的 count 。因此，您将所有候选者的找到的除数一起计算，同时您想单独计算每个候选者。

Answer 3

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

int primegen(unsigned int down,unsigned int up)
{   
int *ar;
int divisor,candidate,count=0,k;

for(candidate=up;candidate>=down;candidate--)
    {   count=0; 
        for(divisor=2;divisor<candidate;divisor++)
            {if (((candidate%divisor)==0)) count++; }
            if(count==0) {printf("%d\n",candidate); count=0;}

    }
}
int main()
{
primegen(3,15);
return 0;
}

最后我纠正了我的解决方案。主要问题是我在第二个 for 循环之前没有将计数分配为零。我改变了候选的顺序（从大到小），并纠正了一些语法错误。

感谢大家的鼓励性帮助和回答。 :) 我很高兴完成这件事，这样我就可以解决其他算法和问题。

Answer 4

一些需要记住的提示

if(!(candidate & 0x01))
    // We know its even so we can stop

if(candidate == potential_factor)
    // We can stop

if(candidate % potential_factor == 0)
    // The potential factor IS a factor and we can stop

Answer 5

为了清楚起见，有人重新格式化了代码，使其不同于原始提交的形式。在此过程中，他们修改了代码中的三个错误之一。

第一个错误是第二个 for 语句后面没有括号。因此，循环体仅包含第二个 for 语句后面的语句。通过阅读代码，很明显提问者希望重复执行第二个循环语句之后的所有内容。事实并非如此。

本质上，这个想法是：对于范围内的每个数字，尝试 1 和候选数字之间的所有数字。数一下分割它的人数。看看是否正好有 2。这是一个正确的算法，而说不除以 2 的答案是错误的。

然而，实现是这样做的：对于范围内的每个数字，将候选值除以 1 和候选值之间的每个数字。然后，完成所有除法后，检查最后一个结果是否为偶数，如果是，则在计数中加 1。所以，发生的情况是，您实际上只是在检查 candidate % Candidate == 0 是否如此，它总是这样做。

第二个错误是计数仅在达到 2 时才重置。因此，对于任何输入，代码都会返回每隔一个的数字。对于每个候选者，count++ 只发生一次。所以它达到 2 并且每隔一段时间就会重置一次。

第三个错误是，一旦最内层循环被修复，那么 continue 就会做错误的事情，因为它只继续最内层循环。

Answer 6

我知道您的代码仅用于教育目的，但是您应该考虑埃拉托斯特尼筛法，因为它可能是解决您的问题的最快算法。它的基本作用是：

1. 首先考虑所有数字素数。
2. 从 2 开始，您认为质数的所有倍数都不是质数。
3. 转到下一个质数，并将其所有倍数设为非质数。

我认为通过阅读以下内容您会更好地理解该算法：
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

至于实现，只需使用数组，其所有元素设置为零，并将从素数到素数的元素设置为 1。

希望这有帮助！