C - Prime Numbers

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_C

問題文

$n$ 個の整数を読み込み、それらの中に含まれる素数の個数を出力するプログラムを作成してね。

制約

• $1 \le n \le 10000$
• $2 \le x_i \le 10^8$

サンプル

I/O 1

6
2
3
4
5
6
7

4

考察

素数判定は、$O(\sqrt{x})$ でできるのでそのまま。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_1_C/judge/6379616/C++17

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

int main() {
  int n;
  cin >> n;
  int ans = 0;
  rep(i, n) {
    int x;
    cin >> x;
    if (isPrime(x)) ans++;
  }
  cout << ans << endl;
  return 0;
}