競プロノート

Appearance

素数判定（Primality Test） ​

整数Nが素数かどうかを判定する。

1つの整数を判定する場合、√Nまでの試し割りで求められる。

特徴 ​

項目内容
用途素数判定
計算量O(√N)
空間計算量O(1)
前処理不要

考え方 ​

Nが合成数なら、N = a × b と表せる。

このとき、aとbの少なくとも一方は√N以下。

したがって、√N以下の整数で割り切れなければ素数と判定できる。

2以外の偶数は素数ではないため、奇数だけ調べればよい。

実装 ​

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool is_prime(ll n) {
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (ll p = 3; p <= n / p; p += 2) {
        if (n % p == 0) return false;
    }
    return true;
}

int main() {
    ll n;
    cin >> n;
    cout << (is_prime(n) ? "Yes" : "No") << '\n';
}

使用例 ​

cpp
is_prime(1);   // false
is_prime(2);   // true
is_prime(97);  // true
is_prime(100); // false

注意点 ​

  • 0と1は素数ではない。
  • 2は唯一の偶数の素数。
  • √Nまで調べれば十分。
  • p * p <= n はオーバーフローする可能性があるため、p <= n / p を使用すると安全。
  • 多数の整数を判定するなら、エラトステネスの篩が有効。
  • 10^18程度の巨大な整数には試し割りは遅いため、Miller-Rabin法などを検討する。

関連 ​