小编典典

Eratosthenes算法筛

algorithm

我目前正在阅读 “编程:使用C ++的原理和实践” ,在 第4章中 有一个练习,其中:

我需要编写一个程序,使用Eratosthenes算法的Sieve算法来计算1到100之间的质数。

这是我想出的程序:

#include <vector>
#include <iostream>

using namespace std;

//finds prime numbers using Sieve of Eratosthenes algorithm
vector<int> calc_primes(const int max);

int main()
{
    const int max = 100;

    vector<int> primes = calc_primes(max);

    for(int i = 0; i < primes.size(); i++)
    {
        if(primes[i] != 0)
            cout<<primes[i]<<endl;
    }

    return 0;
}

vector<int> calc_primes(const int max)
{
    vector<int> primes;

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

    for(int i = 0; i < primes.size(); i++)
    {
        if(!(primes[i] % 2) && primes[i] != 2)
             primes[i] = 0;
        else if(!(primes[i] % 3) && primes[i] != 3)
             primes[i]= 0;
        else if(!(primes[i] % 5) && primes[i] != 5)
             primes[i]= 0;
        else if(!(primes[i] % 7) && primes[i] != 7)
             primes[i]= 0;
    }

    return primes;
}

虽然不是最好的还是最快的,但是我还很早就开始学习本书,并且对C ++不太了解。

现在的问题是,直到max不大于500控制台上打印的所有值为止(如果max > 500不是全部的话)。

难道我做错了什么?

PS:同样,任何建设性的批评也将不胜感激。


阅读 263

收藏
2020-07-28

共1个答案

小编典典

我不知道为什么您没有获得所有输出,因为看起来您应该获得所有输出。您缺少什么输出?

筛网安装错误。就像是

vector<int> sieve;
vector<int> primes;

for (int i = 1; i < max + 1; ++i)
   sieve.push_back(i);   // you'll learn more efficient ways to handle this later
sieve[0]=0;
for (int i = 2; i < max + 1; ++i) {   // there are lots of brace styles, this is mine
   if (sieve[i-1] != 0) {
      primes.push_back(sieve[i-1]);
      for (int j = 2 * sieve[i-1]; j < max + 1; j += sieve[i-1]) {
          sieve[j-1] = 0;
      }
   }
}

将实施筛子。(上面的代码写在我的头上;不保证可以工作甚至编译。我认为第4章末尾没有涉及任何内容。)

primes照常返回,并打印出全部内容。

2020-07-28