C++で素数列挙！O( N √N )編

以前、C++で素数判定！を書いたのですが、
今回は C++で素数列挙！O( N √N ) のコードを書いたのでメモとして残します。

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

N - 1個の自然数の中から素数だけ Pick upして vector に格納後、main関数内で出力しています。*1
計算量は、O( N )個の数に対して O( √N ) 時間かけて探索するので O( N √N ) です。

実行確認：[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

*1:素数をvectorに格納するのを目的としたコードなので､出力は確認用として書きました。