這個算法實現有什麼問題[Erathosthene的篩選]

Question

我試圖在C++中實現Sieve of Eratosthene。然而，經過多次嘗試，我總是得到運行時錯誤。我認爲這與使用迭代器的狀態在某處遭到破壞有關。儘管如此，我仍然無法忍受。這裏是我的代碼：

//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：刪除的東西約擦除（）無效其他迭代器（看起來他們是在這種情況下是安全的） - 只是elements_iter設置爲從擦除的返回值（）和你應該很好走。

Answer 2

num_list.erase(elements_iter) 

我不認爲你應該這樣做，這會從你的列表中完全刪除數字，你寧願要將它標記爲非素數。

如果你真的想用STL代替布爾數組，最好使用std :: bitset，就像this implementation（好吧，也許還有更好的）。

Answer 3

我想我看到一個問題，它是std :: list.erase（）。擦除（）使刪除的迭代器無效只有 - 所有其他部分的迭代器都是有效的。刪除它之後，您繼續在for語句中使用它 - 「elements_iter！= num_list.end（）」。

爲了解決您可以使用的事實，即擦除（）返回迭代器後擦除一個或結束如果擦除oiterator是最後一個。因此，替換行：

num_list.erase（elements_iter）;

通過

elements_iter = num_list.erase（elements_iter）;

如果您仍有問題，我建議您在Visual Studio下調試算法 - 它具有degub版本的STL，所以如果錯誤調試程序會在線路上停止導致問題。

Answer 4

我不知道你爲什麼在這裏使用一個列表。在vector上運行篩選並將素數保存在列表中更容易。

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 5

我已經發布了更高效的篩子previously。

---

這適用於我。從代碼中進行顯着修改：使用.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; 
}