is_prime

関数 · 素数列挙・判定

constexpr bool is_prime(std::uint64_t x);

概要

素数判定

Miller-Rabin 法。std::uint64_t の全域で正しい

計算量

• $O(\log x)$ 回のmod乗算

関連項目

• prime_factorization — 素因数分解
• divisors — 約数列挙
• multiplicative_partitions — 乗法的分割
• Sieve — 素数の篩