7K12 blog

猫でも分かるアルゴリズム解説

数学ライブラリまとめ NTL_Math

素数列挙(素数テーブル)
調和級数を使って閉区間[2, N]の素数 O(\sqrt 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;
	};
}

実装例
https://atcoder.jp/contests/abc250/submissions/31615782