Алгоритм сита Эратосфена

Question

Я сейчас читаю "Программирование: принципы и практика с использованием C ++" , в Глава 4 есть упражнение, в котором:

Мне нужно создать программу для вычисления простых чисел от 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 не все напечатано.

Я что-то не так делаю?

П.С .: Также будет приветствоваться любая конструктивная критика.

Answer 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 как обычно и распечатайте все содержимое.

Answer 2

Думайте о сите как о наборе.
Пройдите набор по порядку. Для каждого значения в исключении удаляются все числа, которые делятся на него.

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

}

Answer 3

Интересно, что никто не ответил на ваш вопрос о проблеме вывода. Я не вижу в коде ничего, что могло бы повлиять на вывод в зависимости от значения max.

Для чего это стоит, на моем Mac я получаю весь вывод. Конечно, это неправильно, поскольку алгоритм неверен, но я все же получаю. Вы не упоминаете, на какой платформе вы работаете, что может быть полезно, если у вас по-прежнему будут проблемы с выводом.

---

Вот версия вашего кода, минимально модифицированная в соответствии с действующим алгоритмом 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;
}

Answer 4

Из Алгоритмы и структуры данных :

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

Answer 5

В приведенном ниже фрагменте кода числа фильтруются перед тем, как вставляться в vector. Делители происходят от вектора.

Я также передаю вектор по ссылке . Это означает, что огромный вектор не будет скопирован из функции в вызывающую функцию. (Большие куски памяти занимают много времени для копирования)

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

Это не самый эффективный алгоритм, но он следует алгоритму Sieve .

Answer 6

Вот краткая, хорошо объясненная реализация с использованием типа bool:

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

покрытие массива. Реализация std::vector будет включать незначительные изменения, такие как сведение функций к одному параметру, через который вектор передается по ссылке, и циклы будут использовать функцию-член vector size() вместо сокращенного параметра.

Answer 7

ниже - моя версия, которая в основном использует битовый вектор 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;
}

Answer 8

Вот классический метод для этого,

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

Answer 9

Вот моя версия:

#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] << ',';
    }
}

Answer 10

Я следую за той же книгой сейчас. Я придумал следующую реализацию алгоритма.

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