test/aoj/challenge/0009.test.cpp

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/0009
#include <iostream>
#include "algorithm/prefix_sum.hpp"
#include "number_theory/prime_number.hpp"

Sieve<1000000> sieve;

int main(void) {
    int n = 1000000;
    std::vector<int> v(n);
    for (int i = 2; i < n; ++i) v[i] = sieve.is_prime(i);
    PrefixSum<int> ps(v);
    int x;
    while (std::cin >> x) std::cout << ps.sum(x + 1) << std::endl;

    return 0;
}