素数判定(Is-Prime)

説明

素数判定

計算量

• $O(\sqrt N)$

実装例

• is_prime($x$):= $x$ が素数なら $true$、それ以外なら $false$ を返す。

bool is_prime(int64_t x) {
  for(int64_t i = 2; i * i <= x; i++) {
    if(x % i == 0) return false;
  }
  return true;
}

検証

AOJ ALDS_1_1_C 素数

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C"

#include "../../template/template.cpp"

#include "../is-prime.cpp"

int main() {
  int N;
  cin >> N;
  int ret = 0;
  while(N--) {
    int x;
    cin >> x;
    ret += is_prime(x);
  }
  cout << ret << endl;
}