ヒント: この問題の最後のサンプルは最大ケースです。
サンプルに最大ケースが入っている場合、そこから何らかの情報を読み取ったり最大ケースに対して正解できるかの判定が(提出前に)行えたりします。

重要な観察として、以下が挙げられます。
\(2^2 \times 3 \times c^2 \le 10^{12}\) より、 \(c \le 288675\)

つまり、まずは \(3 \times 10^5\) 以下の素数を列挙した配列 \(P\) (1-indexed とします) を用意することになりそうです。これはエラトステネスの篩を用いて実現可能です。そして \(3 \times 10^5\) 以下の素数は全部で \(25997\) 個です。

このとき、以下のアルゴリズムを考えます。

• \(i=1\) から \(|P|\) ( \(=P\) のサイズ ) まで以下を繰り返す。
  • 変数 \(k = |P|\) を用意する。
  • \(j<k\) が満たされる限り、 \(j=i+1\) から \(|P|\) まで以下を繰り返す。
    • \(P_i^2 \times P_j \times P_k^2 > N\) かつ \(j<k\) である限り、 \(k\) を \(1\) 減算することを繰り返す。
    • \(j < k' \le k\) なる全ての整数 \(k\) について \(P_i ^2 \times P_j \times P_{k'}^2\) が答えとなるので、答えに \(k-j\) を加算して \(j\) ループを進める。

これにより漏れなくダブりなく数え上げることができます。
時間計算量を \(O(|P|^2)\) と評価でき、この評価からでもギリギリ実行制限に間に合いそうという結論を得ますが実際は \(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++){
    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;
}