C++ 埃拉托色尼筛法

Sieve of Eratosthenes algorithm

提问by RaouL

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

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

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

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

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++.

不是最好的或最快的，但我还处于本书的早期，对 C++ 了解不多。

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

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

Am I doing something wrong?

难道我做错了什么？

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

PS：也将不胜感激任何建设性的批评。

采纳答案by David Thornley

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.)

将实施筛分。（上面的代码在我的头顶上写了下来；不能保证工作甚至编译。我认为它没有任何未在第 4 章结尾处涵盖的内容。）

Return primesas usual, and print out the entire contents.

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

回答by Martin York

Think of the sieve as a set.
Go through the set in order. For each value in thesive remove all numbers that are divisable by it.

把筛子想象成一个集合。
按顺序浏览集合。对于 thesive 中的每个值，删除所有可以被它整除的数字。

#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>


typedef std::set<int>   Sieve;

int main()
{
    static int const max = 100;

    Sieve   sieve;

    for(int loop=2;loop < max;++loop)
    {
        sieve.insert(loop);
    }


    // A set is ordered.
    // So going from beginning to end will give all the values in order.
    for(Sieve::iterator loop = sieve.begin();loop != sieve.end();++loop)
    {
        // prime is the next item in the set
        // It has not been deleted so it must be prime.
        int             prime   = *loop;

        // deleter will iterate over all the items from
        // here to the end of the sieve and remove any
        // that are divisable be this prime.
        Sieve::iterator deleter = loop;
        ++deleter;

        while(deleter != sieve.end())
        {
            if (((*deleter) % prime) == 0)
            {
                // If it is exactly divasable then it is not a prime
                // So delete it from the sieve. Note the use of post
                // increment here. This increments deleter but returns
                // the old value to be used in the erase method.
                sieve.erase(deleter++);
            }
            else
            {
                // Otherwise just increment the deleter.
                ++deleter;
            }
        }
    }

    // This copies all the values left in the sieve to the output.
    // i.e. It prints all the primes.
    std::copy(sieve.begin(),sieve.end(),std::ostream_iterator<int>(std::cout,"\n"));

}

回答by Mark Bessey

Interestingly, nobody seems to have answered your question about the output problem. I don't see anything in the code that should effect the output depending on the value of max.

有趣的是，似乎没有人回答你关于输出问题的问题。我在代码中看不到任何应该根据 max 的值影响输出的内容。

For what it's worth, on my Mac, I get all the output. It's wrong of course, since the algorithm isn't correct, but I do get all the output. You don't mention what platform you're running on, which might be useful if you continue to have output problems.

无论如何，在我的 Mac 上，我得到了所有的输出。这当然是错误的，因为算法不正确，但我确实得到了所有输出。您没有提及您正在运行的平台，如果您继续遇到输出问题，这可能会很有用。

---

---

Here's a version of your code, minimally modified to follow the actual Sieve algorithm.

这是您的代码的一个版本，经过最低限度的修改以遵循实际的 Sieve 算法。

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

    // fill vector with candidates
    for(int i = 2; i < max; i++)
    {
        primes.push_back(i);
    }

    // for each value in the vector...
    for(int i = 0; i < primes.size(); i++)
    {
        //get the value
        int v = primes[i];

        if (v!=0) {
            //remove all multiples of the value
            int x = i+v;
            while(x < primes.size()) {
                primes[x]=0;
                x = x+v;
            }
        }
    }
    return primes;
}

回答by Eric J.

From Algorithms and Data Structures:

从算法和数据结构：

void runEratosthenesSieve(int upperBound) {
      int upperBoundSquareRoot = (int)sqrt((double)upperBound);
      bool *isComposite = new bool[upperBound + 1];
      memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
      for (int m = 2; m <= upperBoundSquareRoot; m++) {
            if (!isComposite[m]) {
                  cout << m << " ";
                  for (int k = m * m; k <= upperBound; k += m)
                        isComposite[k] = true;
            }
      }
      for (int m = upperBoundSquareRoot; m <= upperBound; m++)
            if (!isComposite[m])
                  cout << m << " ";
      delete [] isComposite;
}

回答by Thomas Matthews

In the code fragment below, the numbers are filtered before they are inserted into the vector. The divisors come from the vector.

在下面的代码片段中，数字在插入到vector. 除数来自向量。

I'm also passing the vector by reference. This means that the huge vector won't be copied from the function to the caller. (Large chunks of memory take long times to copy)

我也通过引用传递向量。这意味着巨大的向量不会从函数复制到调用者。 （大块内存需要很长时间才能复制）

vector<unsigned int> primes;

void calc_primes(vector<unsigned int>& primes, const unsigned int MAX)
{
    // If MAX is less than 2, return an empty vector
    // because 2 is the first prime and can't be placed in the vector.
    if (MAX < 2)
    {
         return;
    }

    // 2 is the initial and unusual prime, so enter it without calculations.
    primes.push_back(2);
    for (unsigned int number = 3; number < MAX; number += 2)
    {
        bool is_prime = true;
        for (unsigned int index = 0; index < primes.size(); ++index)
        {
            if ((number % primes[k]) == 0)
            {
                is_prime = false;
                break;
            }
        }

        if (is_prime)
        {
            primes.push_back(number);
        }
    }    
}

This not the most efficient algorithm, but it follows the Sievealgorithm.

这不是最有效的算法，但它遵循Sieve算法。

回答by bHymanfly

below is my version which basically uses a bit vector of bool and then goes through the odd numbers and a fast add to find multiples to set to false. In the end a vector is constructed and returned to the client of the prime values.

下面是我的版本，它基本上使用 bool 的位向量，然后通过奇数和快速添加来查找倍数以设置为 false。最后，构造一个向量并将其返回给质数的客户端。

std::vector<int>  getSieveOfEratosthenes ( int max )
{
  std::vector<bool> primes(max, true);
  int sz = primes.size();

  for ( int i = 3; i < sz ; i+=2 )
    if ( primes[i] ) 
      for ( int j = i * i; j < sz; j+=i)
        primes[j] = false;

  std::vector<int> ret;
  ret.reserve(primes.size());
  ret.push_back(2);

  for ( int i = 3; i < sz; i+=2 )
    if ( primes[i] )
      ret.push_back(i);

  return ret;
}

回答by Ziezi

Here is a concise, well explained implementation using booltype:

这是一个使用booltype的简洁、解释清楚的实现：

#include <iostream>
#include <cmath>

void find_primes(bool[], unsigned int);
void print_primes(bool [], unsigned int);

//=========================================================================
int main() 
{
    const unsigned int max = 100;
    bool sieve[max];

    find_primes(sieve, max);

    print_primes(sieve, max);
}
//=========================================================================

/*
    Function: find_primes()
    Use: find_primes(bool_array, size_of_array);

    It marks all the prime numbers till the
    number: size_of_array, in the form of the
    indexes of the array with value: true.

    It implemenets the Sieve of Eratosthenes,
    consisted of:

    a loop through the first "sqrt(size_of_array)"
    numbers starting from the first prime (2).

    a loop through all the indexes < size_of_array,
    marking the ones satisfying the relation i^2 + n * i
    as false, i.e. composite numbers, where i - known prime 
    number starting from 2.
*/
void find_primes(bool sieve[], unsigned int size)
{
    // by definition 0 and 1 are not prime numbers
    sieve[0] = false;
    sieve[1] = false;

    // all numbers <= max are potential candidates for primes
    for (unsigned int i = 2; i <= size; ++i)
    {
        sieve[i] = true;
    }

    // loop through the first prime numbers < sqrt(max) (suggested by the algorithm)
    unsigned int first_prime = 2;
    for (unsigned int i = first_prime; i <= std::sqrt(double(size)); ++i)
    {
        // find multiples of primes till < max
        if (sieve[i] = true)
        {
            // mark as composite: i^2 + n * i 
            for (unsigned int j = i * i; j <= size; j += i)
            {
                sieve[j] = false;
            }
        }
    }
}

/*
    Function: print_primes()
    Use: print_primes(bool_array, size_of_array);

    It prints all the prime numbers, 
    i.e. the indexes with value: true.
*/
void print_primes(bool sieve[], unsigned int size)
{
    // all the indexes of the array marked as true are primes
    for (unsigned int i = 0; i <= size; ++i)
    {
        if (sieve[i] == true) 
        {
            std::cout << i <<" ";
        }
    }
}

covering the array case. A std::vectorimplementation will include minor changes such as reducing the functions to one parameter, through which the vector is passed by reference and the loops will use the vector size()member function instead of the reduced parameter.

覆盖阵列情况。甲std::vector实现将包括作为减少功能的一个参数，通过这些向量通过引用传递微小的变化，例如并且所述环路将使用矢量size()代替减少的参数成员函数。

回答by scientific_explorer

I am following the same book now. I have come up with the following implementation of the algorithm.

我现在正在关注同一本书。我想出了以下算法的实现。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
inline void keep_window_open() { char ch; cin>>ch; }

int main ()
{
    int max_no = 100;

    vector <int> numbers (max_no - 1);
    iota(numbers.begin(), numbers.end(), 2);

    for (unsigned int ind = 0; ind < numbers.size(); ++ind)
    {
        for (unsigned int index = ind+1; index < numbers.size(); ++index)
        {
            if (numbers[index] % numbers[ind] == 0)
            {
                numbers.erase(numbers.begin() + index);
            }
        }
    }
    cout << "The primes are\n";
    for (int primes: numbers)
    {
        cout << primes << '\n';
    }
}

回答by Luo_xiao

Here is my version:

这是我的版本：

#include "std_lib_facilities.h"
//helper function:check an int prime, x assumed positive.
bool check_prime(int x) {
    bool check_result = true;
    for (int i = 2; i < x; ++i){
        if (x%i == 0){
            check_result = false;
            break;
        }
    }
    return check_result;
}

//helper function:return the largest prime smaller than n(>=2).
int near_prime(int n) {
    for (int i = n; i > 0; --i) {
        if (check_prime(i)) { return i; break; }
    }
}


vector<int> sieve_primes(int max_limit) {
    vector<int> num;
    vector<int> primes;
    int stop = near_prime(max_limit);
    for (int i = 2; i < max_limit+1; ++i) { num.push_back(i); }
    int step = 2;
    primes.push_back(2);
    //stop when finding the last prime
    while (step!=stop){
        for (int i = step; i < max_limit+1; i+=step) {num[i-2] = 0; }
        //the multiples set to 0, the first none zero element is a prime also step
        for (int j = step; j < max_limit+1; ++j) {
            if (num[j-2] != 0) { step = num[j-2]; break; }
        }
        primes.push_back(step);
    }
    return primes;
}

int main() {
    int max_limit = 1000000;
    vector<int> primes = sieve_primes(max_limit);
    for (int i = 0; i < primes.size(); ++i) {
        cout << primes[i] << ',';
    }
}

回答by Khaled Eid

Here is a classic method for doing this,

这是执行此操作的经典方法，

int main()
{
    int max = 500;
    vector<int> array(max); // vector of max numbers, initialized to default value 0

    for (int i = 2; i < array.size(); ++ i) // loop for rang of numbers from 2 to max
    {
        // initialize j as a composite number; increment in consecutive composite numbers
        for (int j = i * i; j < array.size(); j +=i)
            array[j] = 1;  // assign j to array[index] with value 1
    }

    for (int i = 2; i < array.size(); ++ i) // loop for rang of numbers from 2 to max
        if (array[i] == 0)  // array[index] with value 0 is a prime number
        cout << i << '\n';  // get array[index] with value 0

    return 0;
}