练习有问题吗？

Question

我正在对 Stroustrup 的书做以下练习：

创建一个程序来查找 1 到 100 之间的所有素数。 有一个经典的方法可以做到这一点，称为“埃拉托斯特尼筛法”。 如果您不知道该方法，请上网查找。使用这种方法编写你的程序。

我已经理解了这个练习，但我在如何用 C++ 实现它时遇到了问题。
这是到目前为止的代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){

    vector<int> nonprimi;
    vector<int> primi;

    for(int i=0; i <=100; i++){
        primi.push_back(i);
    }

    int numero = 2;

    for(int i = 0; i < 100; i++){
        numero += 2;
        numero == nonprimi[i];
    }

    numero = 3;
    for(int i = 0; i < 100; i++){
        numero += 3;
        numero == nonprimi[i];
    }

    numero = 5;
    for(int i = 0; i < 100; i++){
        numero += 5;
        numero == nonprimi[i];
   }

   numero = 7;
   for(int i = 0; i < 100; i++){
       numero += 7;
       numero == nonprimi[i];
   }

   for(int i = 0; i < nonprimi.size(); i++){
       if(primi[i] != nonprimi[i])
       cout << "\n" << primi[i] << "\n";
   }

return 0;
}

您能为我提供一些建议来帮助我成功实现该算法吗？

注意：也许我应该再读一遍这一章。

Answer 1

与

primi

向量不同，您在第一个循环中将其推回 101 次并且其大小为 101，而

nonprimi

向量永远不会被推回，因此它的大小保持为零。然后，在接下来的循环中，当您尝试为其元素建立索引时，会抛出“向量下标超出范围”异常。

此外，像这样的表达式

numero == nonprimi[i];

是比较语句，除非它们位于

if

语句或

while

循环的括号内，否则不会完成任何操作。

考虑这个替代方案：

第二个

if

循环中的长

for

语句字面意思是，如果第一个数组（已填充 0 到 99 的所有整数）中的数字是 2、3、5 或 7，或者不能被2、3、5 或 7 中的任意一个，然后将其添加到

primi

向量中。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
    vector<int> nonprimi;
    vector<int> primi;
    for (int i = 0; i < 100; i++)
    {
        nonprimi.push_back(i);
    }
    for (int i = 0; i < nonprimi.size(); i++) {
        if (((nonprimi[i] == 2) || (nonprimi[i] == 3) ||
             (nonprimi[i] == 5) || (nonprimi[i] == 7)) || 
             (nonprimi[i] % 2 != 0) && (nonprimi[i] % 3 != 0) && 
             (nonprimi[i] % 5 != 0) && (nonprimi[i] % 7 != 0)) {

            primi.push_back(i);
        }
    }           

    for (int i = 0; i < primi.size(); i++) {
        cout << primi[i] << " ";
    }

    // or in a more STL way
    // copy(primi.begin(), primi.end(), ostream_iterator<int>(cout, " "));

    // system("pause");
    return 0;
}

Answer 2

这是我的答案，不确定是否理想：

#include <vector>
#include <iostream>
using namespace std;

int main()
{
    // Find the prime numbers from 2, 3, 4, 5, through 100
    // using Sieve of Eratosthenes
    
    vector <int> numbers;

    for (int i = 2; i <= 100; i++)
        numbers.push_back(i);

    int p = 0;  // index of "numbers"

    cout << "Prime numbers:\n";
    while (p < (numbers.size() - 1)) {
        int prime = numbers[p];

        for (int i = p + prime; i < numbers.size(); i += prime)
        {
            numbers[i] = -1;    // make all non-prime numbers less than zero
        }

        
        do {
            if (p < (numbers.size() - 1)) {
                p++;    // increase the index until you encounter a positive number
            }
            else
                break;
        } while (numbers[p] < 0);
        cout << prime << endl;
    }
    

}

Answer 3

根据这本书的当前水平和我的经验，我得出以下结论：

int max{ 100 };
vector <int> numbers;
vector <int> multiples;

for (int i = 2; i < max; ++i)                              
{
    numbers.push_back(i);
}


for (int a = 0; a < 6; ++a)                   //is sufficent generate multiples up to 7
{
    for (int x = 1; x < max; x++)
    {
            multiples.push_back(numbers[a] * x);    
    }
    for (int i = 0; i < multiples.size(); ++i)
    {
        for (int x = 0; x < numbers.size(); ++x)
        {
                            
            if (numbers[x] == multiples[i] )
            {
                if (numbers[x] == 0) break;          //increase efficiency
                if (numbers[x] != multiples[0] )     // keeping the first number
                {
                    numbers[x] = 0;               // flagging the multiples
                }
            }
        }
    }
    multiples.clear();   // the vector is emptied to receive multiples of the next number
    
}


for (int x : numbers) if (x != 0) cout << x << " ";     // flagged numbers are not printed
cout << "\n";

向量的使用肯定不是很有效..我设法通过限制倍数的计算不高于7作为方法本身的要求并通过在迭代是多余的地方插入一个中断来解决这个问题（非常轻微......）。 就我而言，事情并不简单。显然，事后，在网上查看一切似乎都是显而易见的，但最初绝对是，溢出是一个常数。 无论如何，如果我对这个主题有了更多的熟悉，我就很满意了