数論 エラトステネスの篩 素数判定 素数

素数判定

素数判定
Feb. 2, 2020, 1:51 p.m.

目次

用途

ある与えられた整数が素数かどうかを高速に判定する.

アルゴリズム1

解説

素数ではない数$x$は必ず$\sqrt{x}$以下の素因数$p$を持つという性質があるので、$\sqrt{x}$以下の整数すべてについて$x$を割り切れるかどうか確認すれば良い.
割り切れる場合は素数ではない数である.
最後まで割り切れる数が現れない場合は素数である.

素数の定義より、1は素数ではない.
2以外の偶数は2で割り切れるので素数でありえない.

計算量

$$
O(\displaystyle\sum_{n=0}^x \sqrt{n})
$$

コード

1
2
3
4
5
6
7
8
9
bool isPrime(Int x) {
  if (x == 1) return false;
  if (x == 2) return true;
  if (x % 2 == 0) return false;

  Int sqrtX = Int(sqrt(x));
  for (Int n = 3; n <= sqrtX; n += 2)  if (x % n == 0) return false;
  return true;
}

アルゴリズム2

エラトステネスの篩(ふるい)と呼ばれるアルゴリズム.

解説

多数の数が素数かどうか判定する場合は事前にテーブルを作成しておいたほうがいい場合もある.

入力として想定される最大値を$X$とおく.
$X+1$分のメモリが必要になる.

($+1$の意味: あとから素数判定する際に31ならisPrime[31]と直感的に使えるようにするために0で下駄を履かせる.)

  • $X+1$の長さのvector<bool> isPrimeを全要素trueで初期化する.trueは素数であることを表す。
  • 0番目と1番目は素数でないのでfalseをセットする.
  • $X$の平方根sqrtXを求める
  • n = 2からsqrtXまで以下を実行する

    • isPrime[n]trueなら、その数はそのままでそれ以降のその数の倍数をすべてfalseにする

あとは、整数$x$の素数判定をしたい場合はisPrime[x]で求められる.

計算量

テーブルの構築

$$
O(N \log \log N)
$$

判定

$$O(1)$$

コード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#define MAX_X 100000001
vector<bool> isPrime(MAX_X, true);

void eratosthenes(vector<bool> &isPrime) {
  Int x = isPrime.size()-1;
  Int x_sqrt = int(sqrt(x));
  isPrime[0] = isPrime[1] = false;
  loop(i,2,x_sqrt+1) {
    if (isPrime[i]) {
      for(Int j = i*2; j <= x; j += i) {
        isPrime[j] = false;
      }
    }
  }
}

isPrime[31]; // -> true