素数判定
(library/number/prime/prime_test.hpp)

• View this file on GitHub
• Last update: 2026-01-15 10:11:56+09:00
• Include: #include "library/number/prime/prime_test.hpp"

素数判定

できること

• 整数Nが素数であるかどうかを判定する

計算量

$O(\sqrt N)$

使い方

bool is_prime = prime_test(N);

Verified with

• エラトステネスの篩のテスト (tests/number.prime.eratosthenes.test.cpp)
• 素数判定のテスト (tests/number.prime.prime_test.test.cpp)

Code

#pragma once
bool prime_test(int N) {
    if (N == 2) return true;
    if (N == 1 or N % 2 == 0) return false;
    for (int i = 3; i * i <= N; i += 2) {
        if (N % i == 0) return false;
    }
    return true;
}

#line 2 "library/number/prime/prime_test.hpp"
bool prime_test(int N) {
    if (N == 2) return true;
    if (N == 1 or N % 2 == 0) return false;
    for (int i = 3; i * i <= N; i += 2) {
        if (N % i == 0) return false;
    }
    return true;
}

Back to top page