みさご解体新書

素数判定（試し割り）

コード例

C++

using ll = long long;

bool is_prime(ll n) {
  if (n <= 1) {
    return false;
  }
  if (n == 2) {
    return true;
  }
  if (n % 2 == 0) {
    return false;
  }

  bool ret = true;
  for (ll i = 3; i * i <= n; i += 2) {
    if (n % i == 0) {
      ret = false;
      break;
    }
  }

  return ret;
}

TypeScript

function isPrime(n: number): boolean {
  if (n <= 1) {
    return false;
  }
  if (n === 2) {
    return true;
  }
  if (n % 2 === 0) {
    return false;
  }

  let ret = true;
  for (let i = 3; i * i <= n; i += 2) {
    if (n % i === 0) {
      ret = false;
      break;
    }
  }

  return ret;
}

解説/アルゴリズム

if (n <= 1) {
  return false;
}
if (n === 2) {
  return true;
}
if (n % 2 === 0) {
  return false;
}

まず、偶数の中で唯一の素数である 2 が渡された場合は true を返し、 1 以下と 2 以外の偶数は素数ではないので false を返す。

let ret = true;
for (let i = 3; i * i <= n; i += 2) {
  if (n % i === 0) {
    ret = false;
    break;
  }
}

return ret;

3, 5, 7, 9... と、奇数で割れないかどうかを確かめる。

n がある値 a で割り切れる場合、 n / a の値でも割り切れるので、上記のように小さい奇数の値から割れるかどうかを確かめていき、 n\sqrt{n} まで見て割り切れなかったら、渡された値が素数であることがわかる。