数学ライブラリまとめ NyaaLIB_NTL

素数判定

任意の値 x が素数かどうか で求める

#include <bits/stdc++.h>

namespace NyaaLIB_NTL
{
	namespace IsPrime
	{
		using ll = long long;
		auto is_prime = [&](ll x) -> bool
		{	// x が素数か判定 O(√x)
			if (x <= 1) return false;
			for (ll i = 2; i * i <= x; i++) if (x % i == 0) return false;
			return true;
		};
	}
}

素数列挙

半開区間[0, n)の素数を で全列挙する
正確な計算量は https://manabitimes.jp/math/992

• 戻り値

res[x] が 1 のとき x は素数
res[x] が 0 のとき x は素数ではない

#include <bits/stdc++.h>

namespace NyaaLIB_NTL
{
	namespace PrimeTable
	{
		using ll = long long;
		auto ptable = [&](ll n) -> std::vector<ll>
		{	// 半開区間[0,n)の素数を返す、計算量 O(n)
			std::vector<ll> res(n, 1);
			res[0] = res[1] = 0;
			for (ll i = 2; i * i < n; i++)
			{
				if (!res[i]) continue;
				for (ll j = i + i; j < n; j += i) res[j] = 0;
			}
			return res;
		};
	}
}

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