目次

• 用途
• アルゴリズム1
  • 解説
  • 計算量
  • コード
• アルゴリズム2
  • 解説
  • 計算量
  • コード

# 用途

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

# アルゴリズム1

# 解説

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

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

# 計算量

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

# コード

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

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)$

# コード

#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