素数判定
(math/prime/is_prime.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "math/prime/is_prime.hpp"

概要

素数判定する.

計算量

$O(\sqrt{n})$

使用例

• is_prime(N) : $N$が素数かを返す.
  • 返り値の型 : bool

Verified with

• test/aoj/ALDS1_1_C.isprime.test.cpp

Code

/**
 * @brief 素数判定
 * @docs docs/math/prime/is_prime.md
 */

bool is_prime(long long n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) return false;
    return true;
}

#line 1 "math/prime/is_prime.hpp"
/**
 * @brief 素数判定
 * @docs docs/math/prime/is_prime.md
 */

bool is_prime(long long n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) return false;
    return true;
}

Back to top page