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より)