素数列挙(素数テーブル)
調和級数を使って閉区間[2, N]の素数をで求める
#include <bits/stdc++.h> namespace NTL_Math { auto NTL_PrimeTable = [&](long long n) -> std::vector<long long> { // 閉区間[2,n]の素数を昇順のテーブルで返す、計算量O(√N) std::vector<bool> check(n + 1, true); for (auto i = 2ll; i * i <= n; i++) { if (!check[i]) continue; for (auto j = i + i; j <= n; j += i) check[j] = false; } std::vector<long long> res; for (auto i = 2ll; i < (long long)check.size(); i++) if (check[i]) res.push_back(i); return res; }; }