algorithm-dev

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub today2098/algorithm-dev

:heavy_check_mark: 素数判定
(algorithm/Math/NumberTheory/is_prime.hpp)

概要

自然数 $n$ が素数かどうか判定する.

本実装では「試し割り法 (trial division)」を用いており,計算量は $\mathcal{O}(\sqrt n)$ となる.

参考文献

  1. “試し割り法”. Wikipedia. https://ja.wikipedia.org/wiki/試し割り法.

Verified with

Code

#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
Back to top page