素数判定
任意の値 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; }; } }