筛选Eratosthenes算法 [英] Sieve of Eratosthenes algorithm

问题描述

我目前正在阅读第4章中的编程：使用C ++的原则和实践，其中包括：

我需要使用Sieve of Eratosthenes算法来计算1到100之间的素数。

这是我想出的程序：

  #include< vector& 
 #include< iostream> 
 
 using namespace std; 
 
 //使用Sieve of Eratosthenes算法查找素数
 vector< int> calc_primes（const int max）; 
 
 int main（）
 {
 const int max = 100; 
 
 vector< int> primes = calc_primes（max）; 
 
 for（int i = 0; i  {
 if（primes [i]！= 0）
 cout ;< primes [i]<< endl; 
} 
 
 return 0; 
} 
 
 vector< int> calc_primes（const int max）
 {
 vector< int>素数
 
 for（int i = 2; i  {
 primes.push_back（i）; 
} 
 
 for（int i = 0; i  {
 if（！ ）&& 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; 
} 
  

不是最好的或最快的，但我还早在书中，

现在的问题，直到 max 不大于 500 在控制台上打印所有值，如果 max>

$ b

$

$

解决方案

我不知道为什么你没有得到所有的输出，它看起来像你应该得到的一切。你缺少什么输出？

筛子实施不当。像

 向量< int>筛; 
 vector< int>素数
 
 for（int i = 1; i  sieve.push_back（i）; //你将学习更多有效的方法来处理这个
 sieve [0] = 0; 
 for（int i = 2; i  if（sieve [i-1]！= 0 ）{
 primes.push_back（sieve [i-1]）; 
 for（int j = 2 * sieve [i-1]; j  sieve [j-1] 
} 
} 
} 
  

（上面的代码写在我的头顶部;不保证工作，甚至编译，我不认为它有没有涵盖在第4章的结尾。）

返回 primes 照常，并打印出所有内容。

I am currently reading "Programming: Principles and Practice Using C++", in Chapter 4 there is an exercise in which:

I need to make a program to calculate prime numbers between 1 and 100 using the Sieve of Eratosthenes algorithm.

This is the program I came up with:

#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;
}

Not the best or fastest, but I am still early in the book and don't know much about C++.

Now the problem, until max is not bigger than 500 all the values print on the console, if max > 500 not everything gets printed.

Am I doing something wrong?

P.S.: Also any constructive criticism would be greatly appreciated.

解决方案

I have no idea why you're not getting all the output, as it looks like you should get everything. What output are you missing?

The sieve is implemented wrongly. Something like

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;
      }
   }
}

would implement the sieve. (Code above written off the top of my head; not guaranteed to work or even compile. I don't think it's got anything not covered by the end of chapter 4.)

Return primes as usual, and print out the entire contents.

这篇关于筛选Eratosthenes算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！