Решето Эратосфена Удаление элементов списка

Я работал над книгой Страуструпа: https://rads.stackoverflow.com/amzn/click/com/0321543726 В настоящее время я работаю над упражнением 13 главы 4, в котором вам предлагается реализовать алгоритм решета Эратосфена для нахождения простых чисел между 1 и 100. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Сейчас я пытаясь удалить числа, кратные 2. Я пробовал как функцию стирания, так и remove_if (что вызывает нечетные ошибки сегментации). Я не ищу советов по реализации, просто помогите с удалением элементов векторов.

 #include "std_lib_facilities.h"
#include <math.h>
#include <vector>
/*
This program attempts to find the prime numbers in the range of a value
using the Sieve of Eratosthenes algorithm.
*/
int main() {
    vector<int>primer;
    cout<<"This program calculates prime numbers up until a value max\n"
            "and prints these out."<<endl;
    int max = 100;
    for (int i = 2; i <= max; i += 1) { //creates a list of integers from 2 to 100.
        primer.push_back(i);
    }
    for (int n = 2; n < max; n += 2) { //attempts to delete the multiplies of 2, excluding 2 itself.
       primer.erase(?);
    }
     copy(primer.begin(), primer.end(), ostream_iterator<int>(cout, " "));//prints the elements of the vector
}

Любая помощь приветствуется! Спасибо!


c++ vector erase sieve-of-eratosthenes
person user3171116    schedule 02.04.2014    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Чтобы стереть элементы из контейнеров STL, вам нужно использовать идиому стирания-удаления: http://en.wikipedia.org/wiki/Erase-remove_idiom

    bool is_even(int n) { return 0 == n % 2; }

    int main() 
    {
        ...
        v.erase(std::remove_if(v.begin(), v.end(), is_even), v.end());
        ...
    }

Чтобы удалить любое значение (только не кратное 2), вы можете использовать функциональные объекты или функторы.

    class is_multiple_of
    {
        int m_div;
    public:
        is_multiple_of(int div) : m_div(div) {}
        bool operator()(int n) { return 0 == n % m_div; }
    };

И использовать его:

    v.erase(std::remove_if(v.begin(), v.end(), is_multiple_of(3)), v.end());
    v.erase(std::remove_if(v.begin(), v.end(), is_multiple_of(5)), v.end());
person ganz    schedule 02.04.2014
comment
Спасибо! Именно то, что я искал! Мой вопрос в том, могу ли я определить логическое значение для кратных 3 и 5? - person user3171116; 02.04.2014
comment
Я расширил ответ, чтобы можно было удалить несколько произвольных чисел, см. выше. - person ganz; 02.04.2014

arrow_upward
1
arrow_downward

Из соображений эффективности вы обычно не удаляете элементы в сите эратосфена, а просто отмечаете их как неиспользуемые. На самом деле вам не нужно хранить числа от 1 до 100 (или 1000, или что-то еще) в векторе. Вместо этого установите для каждого члена вектора значение 1 (или 0), а затем установите противоположное значение, чтобы указать, что он был вычеркнут. Числовое значение элемента — это просто его позиция в массиве. Чтобы вычеркнуть каждое n-е число, вы должны просмотреть массив, считая до n снова и снова, отмечая эти числа.

Чтобы распечатать значения, вы просматриваете массив и распечатываете только индексы элементов, которые все еще равны 1.

person ooga    schedule 02.04.2014

arrow_upward
0
arrow_downward

В вашем коде, поскольку вы удаляете кратное 2,3,5,7.... каждый раз, когда размер вашего вектора будет меняться. Я предлагаю вам определить новую переменную int len = primer.size();//In this case it will be equal to Max-2 После этого вы можете erase() обновить вектор.
#include #include #include using namespace std;

/*
This program attempts to find the prime numbers in the range of a value
using the Sieve of Eratosthenes algorithm.
*/
int main() {
    vector<int>primer;
    cout<<"This program calculates prime numbers up until a value max\n"
        "and prints these out."<<"\n";
    int max = 100;
    for (int i = 2; i <= max; i += 1) { //creates a list of integers from 2  to 100.
        primer.push_back(i);
    }
    int len = primer.size();
    for (int i = 2; i < len; ) { //attempts to delete the multiplies of 2, excluding 2 itself.
         if(primer[i]%2==0) {
             primer.erase(primer.begin()+n);
             len = primer.size();
         }
         else
            i++;
}
 copy(primer.begin(), primer.end(), ostream_iterator<int>(cout, " "));//prints the elements of the vector

}

person Shravan40    schedule 02.04.2014