使用集合計算素數，C++

我想用集合來計算素數，但是當我做計算時，我的迭代器隨機跳躍。使用集合計算素數，C++

我想實現這個方法的值爲N = 10。

選擇一個整數n。該函數將計算所有質數至n。首先將所有從1到n的數字插入到一個集合中。然後清除所有的倍數（2除外）;也就是4,6,8,10,12 ....刪除所有的倍數爲3，即6,9,12,15 ......。去sqrt（n）。剩下的數字都是素數。

當我運行我的代碼時，它擦除1然後pos跳轉到4？我不確定爲什麼會發生這種情況，而不是它會轉到集合中第二個值的值2？

另外，在我擦除迭代器指向的值之後會發生什麼，迭代器指向的是什麼，如果我提前它在哪裏前進？

下面是代碼：

set<int> sieveofEratosthenes(int n){ //n = 10 

    set<int> a; 
    set<int>::iterator pos = a.begin(); 

//generate set of values 1-10 
    for (int i = 1; i <= n; i++) { 
     a.insert(i); 
     if(pos != a.end()) 
      pos++; 
    } 

    pos = a.begin(); 

    //remove prime numbers 
    while (pos != a.end()) 
    { 
     cout << "\nNew Iteration \n\n"; 

     for (int i = 1; i < sqrt(n); i++) { 
      int val = *pos%i; 

      cout << "Pos = " << *pos << "\n"; 
      cout << "I = " << i << "\n"; 
      cout << *pos << "/" << i << "=" << val << "\n\n"; 

      if (val == 0) { 
       a.erase(i); 
       } 
      } 
     pos++; 
    } 
    return a; 
}

來源

2015-12-22 user2076774

Eratosthenes的篩沒有使用任何形式的可分性測試。您可以手動執行，而不必知道任何算術。 – molbdnilo

你的實現是在它試圖篩算法的嘗試約數的簡單算法結合不正確的，它這樣做不成功。你不需要測試可分性來實現篩選 - 事實上，這是算法美的主要貢獻者！你甚至不需要乘法。

a.erase(1); 
pos = a.begin(); 
while (pos != a.end()) { 
    int current = *pos++; 
    // "remove" is the number to remove. 
    // Start it at twice the current number 
    int remove = current + current; 
    while (remove <= n) { 
     a.erase(remove); 
     // Add the current number to get the next item to remove 
     remove += current; 
    } 
}

Demo.

來源

2015-12-22 19:28:04 dasblinkenlight

不錯！ 'while（pos！= a.end（）&&（* pos）*（* pos）

確實* pos ++先分配給當前，然後增加後？ – user2076774

@ user2076774 * * pos ++'表現得像一個指針：它在迭代器pos處產生當前值，然後將增加的值存儲到迭代器中。 – dasblinkenlight

當擦除你必須要小心與指數環內的元素。例如，當您在位置0刪除元素，那麼下一個元素是現在所在的位置爲0。因此，循環應該是這個樣子：

for (int i = 1; i < sqrt(n); /*no increment*/) { 
     /* ... */ 
     if (val == 0) { 
      a.erase(i); 
     } else { 
      i++; 
     } 
    }

其實，你也必須照顧的大小在擦除元素時，該設置正在縮小。因此，你最好使用迭代器：

for (auto it = a.begin(); i != a.end(); /*no increment*/) { 
     /* ... */ 
     if (val == 0) { 
      a.erase(it); 
     } else { 
      it++; 
     } 
    }

PS：以上是不是正是你需要什麼篩，但應足以說明如何刪除元素（我希望如此）。

來源

2015-12-22 19:29:38 user463035818

使用集合計算素數，C++

回答

相關問題