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;
}