This documentation is automatically generated by online-judge-tools/verification-helper
#include "algorithm/Math/NumberTheory/is_prime.hpp"
自然数 $n$ が素数かどうか判定する.
本実装では「試し割り法 (trial division)」を用いており,計算量は $\mathcal{O}(\sqrt n)$ となる.
#ifndef ALGORITHM_IS_PRIME_HPP
#define ALGORITHM_IS_PRIME_HPP 1
#include <cassert>
namespace algorithm {
// 素数判定.O(√N).
template <typename Type>
constexpr bool is_prime(Type n) {
assert(n >= 0);
if(n < 2) return false;
if(n == 2) return true;
if(n % 2 == 0) return false;
for(Type p = 3; p * p <= n; p += 2) {
if(n % p == 0) return false;
}
return true;
}
} // namespace algorithm
#endif
#line 1 "algorithm/Math/NumberTheory/is_prime.hpp"
#include <cassert>
namespace algorithm {
// 素数判定.O(√N).
template <typename Type>
constexpr bool is_prime(Type n) {
assert(n >= 0);
if(n < 2) return false;
if(n == 2) return true;
if(n % 2 == 0) return false;
for(Type p = 3; p * p <= n; p += 2) {
if(n % p == 0) return false;
}
return true;
}
} // namespace algorithm