test/verify/aoj-alds-1-1-c-2.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 10:55:59+00:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C
• Link: View error logs on GitHub Actions

Depends on

• Prime Table (素数テーブル) (math/number-theory/prime-table.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C
// clang-format on

#include <iostream>

#include "../../math/number-theory/prime-table.hpp"

using namespace std;

int main() {
  auto t = prime_table(100000000);
  int N;
  cin >> N;
  int ret = 0;
  while (N--) {
    int x;
    cin >> x;
    ret += t[x];
  }
  cout << ret << endl;
}

#line 1 "test/verify/aoj-alds-1-1-c-2.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C
// clang-format on

#include <iostream>

#line 2 "math/number-theory/prime-table.hpp"

#include <vector>

/**
 * @brief Prime Table(素数テーブル)
 *
 */
std::vector<bool> prime_table(int n) {
  std::vector<bool> prime(n + 1, true);
  if (n >= 0) prime[0] = false;
  if (n >= 1) prime[1] = false;
  for (int i = 2; i * i <= n; i++) {
    if (!prime[i]) continue;
    for (int j = i * i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}
#line 8 "test/verify/aoj-alds-1-1-c-2.test.cpp"

using namespace std;

int main() {
  auto t = prime_table(100000000);
  int N;
  cin >> N;
  int ret = 0;
  while (N--) {
    int x;
    cin >> x;
    ret += t[x];
  }
  cout << ret << endl;
}

Back to top page