素数の和 [yukicoder No.713]

https://yukicoder.me/problems/no/713

解法

https://yukicoder.me/submissions/272887

色々な解法が考えうる。
自分の解法ではmakePrimes関数を作って解いた。
makePrimes(n)はn以下の素数の集合を返す関数。

vector<int> makePrimes(int n) {
    vector<int> res, primes(n + 1, 1);
    primes[0] = primes[1] = 0;
    rep(i, 2, sqrt(n)) if (primes[i]) for (int j = 0; i * (j + 2) <= n; j++) primes[i * (j + 2)] = 0;
    rep(i, 2, n + 1) if (primes[i]) res.push_back(i);
    return res;
}

この関数では前半でエラトステネスの篩を使って素数かどうかを判定したあと、素数である数をvectorに入れて返している。
この関数が返した集合の総和を取れば答え。
　
※ 高速な素数判定法としてミラーラビン素数判定法というのもある

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    auto pv = makePrimes(N);
    int ans = 0;
    fore(p, pv) ans += p;
    cout << ans << endl;
}