C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

C++で素数列挙!エラトステネスの篩 編

C++で素数列挙!O( N√N )編 を書きましたが、
今度はもっと高速な エラトステネスの篩(ふるい)編 *1 を書いたのでコードを残します。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#include <vector>
std::vector<int> Eratosthenes( const int N )
{
    std::vector<bool> is_prime( N + 1 );
    for( int i = 0; i <= N; i++ )
    {
        is_prime[ i ] = true;
    }
    std::vector<int> P;
    for( int i = 2; i <= N; i++ )
    {
        if( is_prime[ i ] )
        {
            for( int j = 2 * i; j <= N; j += i )
            {
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}
int main()
{
    int N;
    cin >> N;
    for( const auto &x: Eratosthenes( N ) )
    {
        cout << x << " ";
    }
    return 0;
}

ベースは 蟻本 P112 の「素数の個数」を求めるというコードです。
上記コードは、素数を pick upして vector に格納すると云うものです。
計算量O( N log log N )だそうです。(蟻本 P112より)

実行確認:[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ