Eratosthenes的筛子C++无限循环

所以，我一直在解决Bjarne Stroustrup的编程：使用C++的原则和实践中的一个问题，为了我自己的利益，而且这个问题已经让我困惑了几天。Eratosthenes的筛子C++无限循环

我应该实现埃拉托色尼算法与第四章学到的工具的经典筛（这是不是很多），这是我到目前为止有：

#include <iostream> 
#include <vector> 
#include <cmath> 

using namespace std; 

int main() 
{ 
    int p = 2; 
    int n = 0; 
    vector<int> nums{ 1, 1 }; 

    cout << "Enter an integer greater than 1:\n"; 
    cin >> n; 

    for (int i = 2; i <= n; ++i) 
     nums.push_back(0); 

    while (p < sqrt(n)) 
    { 
     for (int i = 2; (i*p) <= n; ++i) 
     { 
      nums[i*p] = 1; 
     } 

     for (int i = (p+1); i <= n; ++i) 
     { 
      if (nums[i] == 0) 
      { 
       p = i; 
       break; 
      } 
     } 
    } 

    for (int i = 0; i <= n; ++i) 
    { 
     if (nums[i] == 0) 
      cout << i << '\n'; 
    } 

    return 0; 
}

此代码是SOOO接近工作但没有雪茄。它只打印包含5之后的素数，它不打印2或3.我知道问题是由于我的标记循环正在标记nums [2]和nums [3]，所以我尝试添加下面的代码行，以确保2和3为未标记的，因为它们被用作p起始值：

nums[p] = 0;

我把线在中间嵌套的while循环中的两个for循环。我不知道如何，但不知何故导致我已经尝试了几个小时来修复的无限循环。我真的在我的智慧结束了。

注：我已经有n测试这种= 23

来源

2015-10-15 Anthony Rossello

因为你的标记'for'循环开始于'0'，每次你找一个素数，它标志着'0'和'p'也是非主要的。在你的情况下，由于'5> sqrt（23）'，标记循环不会运行于大于'3'的任何素数，所以你得到这些素数，但'2'和'3'是不幸的一些:-) –

感谢您的评论。不幸的是，让我的标记循环从i = 2开始也让我陷入无限循环！ –

当你进行一个重要的更正，比如'i = 0'改为'i = 2'，并且代码仍然无法工作，请编辑原始文章以显示您现在需要帮助的版本。不要只告诉我们你纠正了这个错误，让我们猜测你是否正确纠正了错误。 – JSF

因此，固定你的第一个循环的起点后，这个问题是下一个循环。

由于下一个循环始终始于0并查找下一个素数，它总是会找到2，并且这将导致无限循环。

为了解决这个问题，开始搜索下一个素数，由前值：

for(int i = p + 1; i <= n; ++i)

来源

2015-10-15 21:11:58

Eratosthenes的筛子C++无限循环

回答

相关问题