Что не так с реализацией этого алгоритма [Сито Эратхостена]

Question

Я пытаюсь реализовать Сито Эратосфена в C ++. Однако после нескольких попыток это всегда приводит к ошибкам во время выполнения. Я думаю, что это связано с тем, что используемые итераторы где-то повреждаются. Я не могу положить палец на это, хотя. Вот мой код:

    //Sieves all multiples of  the current sequence element
    bool multiple_sieve(std::list<int>& num_list)
    {
        std::list<int>::iterator list_iter(num_list.begin());
        std::list<int>::reverse_iterator last_element_iter(num_list.rbegin());

        for(std::list<int>::iterator elements_iter(++list_iter);
           elements_iter !=  num_list.end();)
        {
            if((*elements_iter % *list_iter == 0) &&
             (*elements_iter <= *last_element_iter) && (*list_iter != 1))
                num_list.erase(elements_iter);
            else ++elements_iter;
        }
        return true;
    }

    std::list<int>& prime_sieve(std::list<int>& num_list)
    {
        for(std::list<int>::iterator list_iter(num_list.begin());
          list_iter != num_list.end(); ++list_iter)
            multiple_sieve(num_list);
        return num_list;
    }

Что я делаю не так? Что генерирует ошибки времени выполнения?

Обновление: когда я запускаю это в своих тестах, я получаю сообщение об ошибке "Итераторы списка не совместимы".

Answer 1

Эта строка:

num_list.erase(elements_iter);

Это вызовет у вас проблемы, так как вы изменяете список во время его итерации. Вы можете сделать это, чтобы избежать этой проблемы:

elements_iter = num_list.erase(elements_iter);

ETA: Удалено что-то о том, что erase () делает недействительными другие итераторы (похоже, они в этом случае безопасны) - просто установите elements_iter на возвращаемое значение из erase (), и все будет хорошо.

Answer 2

Я не знаю, почему вы используете список здесь. Проще запустить sieve по вектору и сохранить простые числа в списке.

std::list<int> primes(int MAXN){
  std::list<int> result;
  std::vector<bool> sieve(MAXN+1,true);
  for(int i=2;i<=MAXN;i++){
    if(sieve[i]==true){
      result.push_back(i);
      if((long long)i*i<=MAXN)  //prevent integer overflow
        for(int j=i*i;j<=MAXN;j+=i)
          sieve[j]=false;
    }
  }
  return result;
}

Answer 3

Мне кажется, я вижу одну проблему, и это std :: list.erase (). erase () делает недействительным удаленный итератор only - все итераторы для других частей действительны. После того, как вы удалили его, вы продолжаете использовать его для выражения «elements_iter! = Num_list.end ()».

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

num_list.erase (elements_iter);

от

elements_iter = num_list.erase (elements_iter);

Если у вас все еще есть проблема, я советую вам отладить ваш алгоритм под Visual Studio - он имеет разностную версию STL, поэтому в случае ошибки отладчик остановится на линии, вызывая проблему.

Answer 4

Я разместил более эффективное сито ранее .

---

Это работает для меня. Заметные изменения в вашем коде: используйте .erase(i++), в противном случае итератор становится недействительным, и начинайте multiple_sieve с последовательных позиций в списке, а не всегда с начала.

#include <iostream>
#include <list>

template<typename T, typename L>
void multiple_sieve(L &nums,
        const typename L::iterator &begin, const typename L::iterator &end) {
    T first = *begin;
    typename L::iterator i(begin);
    ++i;
    while (i != end)
        if (*i % first == 0) nums.erase(i++);
        else ++i;
}

template<typename T, typename L>
void prime_sieve(L &nums) {
    typename L::iterator end = nums.end();
    for (typename L::iterator i(nums.begin()); i != end; ++i)
        multiple_sieve<T, L>(nums, i, end);
}

int main(int argc, char **argv) {
    std::list<int> list;
    for (int i = 2; i < 1000; i++)
        list.push_back(i);
    prime_sieve<int, std::list<int> >(list);
    for (std::list<int>::iterator i(list.begin());
            i != list.end(); i++)
        std::cout << *i << std::endl;
}

Answer 5

num_list.erase(elements_iter)

Не думаю, что вам следует это делать, это полностью удаляет номер из вашего списка, вы скорее хотите пометить его как не простое число.

Если вы действительно хотите использовать для этого STL вместо массива bool, лучше используйте std :: bitset, как в этой реализации (ну, возможно, есть и лучшие).