Hint: the last sample of this problem is the maximum case.
If the sample includes the maximum case, you can observe something or check if your program works correctly for the maximum case (before submitting.)

Here is an important observation:
\(2^2 \times 3 \times c^2 \le 10^{12}\), so \(c \le 288675\).

Thus, we first need to prepare an array \(P\) of primes up to \(3 \times 10^5\). (We assume 1-indexed array). This can be obtained with Eratosthenes’ sieve. There are \(25997\) primes up to \(3 \times 10^5\).

Then, we consider the following algorithm.

• From \(i=1\) to \(|P|\) (\(=\) size of \(P\)), repeat the following.
  • Prepare a variable \(k = |P|\).
  • While \(j<k\), repeat the following from \(j=i+1\) to \(|P|\).
    • Repeatedly decrement \(k\) by \(1\) while \(P_i^2 \times P_j \times P_k^2 > N\) and \(j<k\).
    • For all integers \(k\) such that \(j < k' \le k\), \(P_i ^2 \times P_j \times P_{k'}^2\), is an answer, so add \(k-j\) to the answer and advance the \(j\) loop.

This way, we can count the numbers without duplicates and missing.
The time complexity is evaluated to be \(O(|P|^2)\), which seems barely fit in the time limit. Actually, most of the part in the \(j\) loop is not scanned, so it works fast enough.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

#define MAXP 300005

vector<long long> sieve(){
  vector<long long> res;
  vector<int> mem(MAXP,0);
  for(int i=2;i<MAXP;i++){
    if(mem[i]){continue;}
    res.push_back(i);
    for(int j=i;j<MAXP;j+=i){mem[j]=1;}
  }
  return res;
}

int main(){
  vector<long long> p=sieve();
  long long n;
  cin >> n;
  int sz=p.size();
  int res=0;
  for(int i=0;i<sz;i++){
    int k=sz-1;
    for(int j=i+1;j<k && j<sz;j++){
      while(j<k){
        long long v=p[i]*p[i]*p[j]; // <= 10^{18}, won't overflow
        if(v>n){k--;continue;}
        v*=p[k]; // <= 10^{18} because (<= n <= 10^12) * (<= 10^6)
        if(v>n){k--;continue;}
        v*=p[k];
        if(v>n){k--;continue;}
        break;
      }
      res+=(k-j);
    }
  }
  cout << res << "\n";
  return 0;
}

実はこの問題はさらにシンプルに正解することができます。

• \(i=1\) から \(|P|\) まで以下を繰り返す。
  • \(j=i+1\) から \(|P|\) まで以下を繰り返す。
    • \(k=j+1\) から \(|P|\) まで以下を繰り返す。
      • \(P_i^2 \times P_j \times P_k^2 > N\) なら \(k\) ループを終了する。
      • そうでないなら答えに \(1\) 加算する。

これは紛れもなく愚直な \(3\) 重ループによる全探索です。なぜこのコードで正解できるのでしょうか。
実は「 答え \(\le 3 \times 10^6\) 」が最後のサンプルより読み取れるので、ループの回数を \(O(|P|^2 + ans)\) ( \(ans\) は問題の答え) と見積もることが出来ます。
このままでも実行時間制限に間に合い、 \(i\) ループに「 \(P_i^2 \times P_{i+1} \times P_{i+2}^2 > N\) なら \(i\) ループを終了する」、\(j\) ループに「 \(P_i^2 \times P_j \times P_{j+1}^2 > N\) なら \(j\) ループを終了する」というような枝刈りを入れると更に高速になります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

#define MAXP 300005

vector<long long> sieve(){
  vector<long long> res;
  vector<int> mem(MAXP,0);
  for(int i=2;i<MAXP;i++){
    if(mem[i]){continue;}
    res.push_back(i);
    for(int j=i;j<MAXP;j+=i){mem[j]=1;}
  }
  return res;
}

int main(){
  vector<long long> p=sieve();
  long long n;
  cin >> n;
  int sz=p.size();
  int res=0;
  for(int i=0;i<sz;i++){
    for(int j=i+1;j<sz;j++){
      for(int k=j+1;k<sz;k++){
        long long v=p[i]*p[i]*p[j];
        if(v>n){break;}
        v*=p[k];
        if(v>n){break;}
        v*=p[k];
        if(v>n){break;}
        res++;
      }
    }
  }
  cout << res << "\n";
  return 0;
}