Hiperprimos

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 2e6+5;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  vector<int> primes;
  vector<int> cnt_primes(MAXV, 0);
  vector<bool> is_prime(MAXV, true);

  is_prime[1] = false;
  for (int i = 2; i < MAXV; ++i) {
    if (is_prime[i]) {
      cnt_primes[i] = 1;
      primes.push_back(i);
      for (int64_t j = (int64_t)i * i; j < MAXV; j += i) {
        is_prime[j] = false;
      }
      for (int64_t j = (int64_t)i * i, c = 2; j < MAXV; j *= i, ++c) {
        cnt_primes[j] = c;
      }
    }
  }

  vector<int> a;
  int x, maxV = -1;

  while (cin >> x) {
    a.push_back(x);
    maxV = max(maxV, x);
  }

  vector<int> ans(maxV + 1, 0);

  for (int i = 2; i <= maxV; ++i) {
    if (is_prime[cnt_primes[i] + 1]) {
      ans[i] = 1;
    }
  }

  for (int i = 2; i <= maxV; ++i) {
    ans[i] += ans[i-1];
  }

  for (int i = 0; i < a.size(); ++i) {
    cout << ans[a[i]] << '\n';
  }
}