C++ STL:找質數 ( Prime Number with C++ STL )

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

因為STL的 iteractor 算是指標(還是有差異),那麼就可以先將有可能成為質數的整數都放進vector裡,然後採埃拉托斯特尼篩法加上雙指標將非質數的整數給刪除。

/*
  Prime Number using STL
*/

#include <iostream>
#include <functional>
#include <algorithm>
#include <iterator>
#include <vector>

using namespace std;

int main( void)
{
    vector< int> primes;
    int n;
    cin >> n;
    for(int i= 2; i <= n; i++)
        primes.push_back(i);

    vector<int>::iterator primeBegin= primes.begin(),
                           primeEnd= primes.end();

    while( primeBegin != primeEnd )
    {
        primeEnd= remove_if( primeBegin+ 1, primeEnd,
                           not1( bind2nd( modulus<int>(), *primeBegin)));

        primeBegin++;
    }

    primes.erase( primeEnd, primes.end());

    copy( primes.begin(), primes.end(),
          ostream_iterator<int>( cout, " "));
    cout << endl;

    return 0;
}

沒有留言: