-1

我有一个编程任务，用 C++ 编写一个程序，该程序找到所有小于n的素数（用户输入）。一半的任务涉及埃拉托色尼筛。我的代码正在运行（阅读：分配完成），但在我编辑输出之前，它无条件地将n-3、n-2和n-1打印为素数，即使它们不是素数。我不确定为什么会这样。对于程序为何如此运作，我将不胜感激一些反馈和想法。这是未更改的代码：

请注意，我使用的是 ListNode 类和 LinkedList 类，它们都是功能齐全的。编辑：部分主要添加；注意for循环中的第二项是size-3。如果它保留在size，程序会输出 3 个额外的非素数。

int main()
{
    for(int i = 0; i<my_list.size()-3; i++)
    {
        if(marked[i]==true)
            cout<<my_list[i]<<"\n";
    }
}

void eratosthenes(int item)
{
   bool run=true;
   int p=2, count=0;

   for(int i=2; i<=item; i++)
   {
      my_list.append(i);    // Entire list is filled with integers from 2 to n
      marked.append(true);  // Entire list is filled with true entries
   }

   while(run==true&&(2*p)<item)
   {
      count = 0;
      int i = (2*p);

      do {
         marked[i-2]=false;       // marked values are false and not prime
         i+=p;
      } while(i<item-2);

      for(int i=0; i<item-2; i++) // i starts at 0  and increments by 1 
      {                           // each time through the loop
         if(my_list[i]>p)
         {
            if(marked[i]==true)   // If a value stored in a node is true  
            {                     //   (prime), it becomes the new p.
               p=my_list[i];      //   The loop is then broken. 
               break;
            }
         }
      }
      for(int j=1; j<item-2; j++)
      {
         if(marked[j]==false)
         {
            count=1;
         }
      }
      if(count==0)
         run=false;
   }
4

3 回答 3

1

完整方法

    void Eratosthenes(int upperBound)
    {
        bool Prime[upperBound];
        for(int i = 0;i<upperBound;i++)
         Prime[i]=true;

        for (int i = 2; i <= sqrt(upperBound); i++) 
         {
             if (Prime[i]) 
             {
                for (int j = i * 2; j < upperBound; j += i) 
                    Prime[j] = false;

              }
         }
         for(int i=2;i<upperBound;i++)
         {
                 if(Prime[i]==true)
                 cout<<i<<" ";
          }
    }
于 2013-01-27T21:53:02.847 回答
0

从您的代码：

  do{
     marked[i-2]=false;//marked values are false and not prime
     i+=p;
  }while(i<item-2);

据我了解，这个循环负责遍历所有i是素数整数倍的数字p并将它们标记为非素数。你为什么要停止条件i < item - 2？如果您的and列表i是您的索引，这会很好，但在这种情况下它不是；这是您标记的实际数字不是素数。我怀疑这就是为什么你得到的数字接近你的极限（）被标记为素数——你的循环在到达这些数字之前就退出了！my_listmarkeditemi

顺便说一句，您可以将其作为 for 循环来执行，这样更易​​于阅读。for 循环的含义是“遍历集合中的每个元素”（无论是连续整数，还是每第 n 个整数，或数组/列表/双端队列中的元素等），所以阅读您的代码的程序员会立即知道并且不必从您的 while 循环中弄清楚。

// mark every multiple of the current prime as not prime
for(int i = 2*p; i < item - 2; i += p)
{
    marked[i-2] = false;
}

（这与您的原始代码相同，未应用任何修复）。

一些改进您的算法/代码的一般性评论：

尝试使用更具描述性的变量名称。您使用i两次来表示不同的事物令人困惑，并且通常单个字母对于变量所代表的含义并不大（尽管有时它们就足够了，例如 for 循环，其中i列表/数组的索引） .

此外，您对列表的循环次数超出了您的需要。Eratosthenes 算法需要的最小筛选是两个嵌套的 for 循环（不包括将列表/数组初始化为 all true）。

你做的工作比必要的多的一个例子是你从索引 0 开始循环寻找下一个p要使用的——而不是仅仅记住你的电流在哪里p并从那里开始。你甚至不需要检查my_list[i] > p那种情况，因为你知道你会超越它开始。此外，您的最后一个循环可能会break;提前并避免在找到非质数后继续（我不确定它的意义是什么）。

Nikola Mitev 的第二个答案是筛子的更有效和更易读的实现（但替换sqrt(upperBound)为upperBound/2使其正常工作；upperBound/2从筛子的工作方式中应该很清楚的原因），尽管他并没有真正给出太多评论或对它的解释。第一个循环是“遍历每个数字直到上界”；在其中，“如果当前数字是素数，则遍历该素数的所有倍数并将它们标记为非素数”。在内循环执行后，外循环继续，遍历下一个数字——不需要从头开始，甚至不需要输入另一个 for 循环来查找下一个素数。

编辑：sqrt(upperBound)是正确的。我考虑得不够仔细。

于 2013-01-27T22:33:16.997 回答
0

为简单起见，您为什么不使用布尔数组从索引 2 开始，当您打印结果时，您将打印值为 true 的索引

于 2013-01-27T21:32:50.627 回答