公式解説にもあるように、相異なる素数 \(p,q\) を用いて \(p^8\) もしくは \(p^2q^2\) と表せるものが答えです。

入力例2を見ると、答えは最大でも \(407073\) であることがわかります。よって、全列挙が可能です。

\(p,q\) を全探索します。ただし、\(p,q\)は素数です。 \(p^2q^2 \leq N\)より、\(p,q \leq \sqrt{N}\) なので、\(\sqrt{N}\) 以下の素数を列挙できれば、 \(p,q\) を全探索することで答えを求めることができます。

素数の列挙はエラトステネスの篩と呼ばれるアルゴリズムを用いて行うことができます。（「素数列挙　競プロ」などで検索することですぐに見つけることができるため、コンテスト中に知らなかったとしてもこの情報にたどり着くことは可能です）

解法をまとめます。

• エラトステネスの篩を用いて、 \(\sqrt{N}\) 以下の素数を列挙する。（ただし実際には実装の簡略化のため、\(\sqrt{N}\) を計算せずに\(10^6\)以下の素数を列挙する）
• \(2\) 重ループを用いて \(p,q\) を全探索する。
• \(p^2q^2\) が \(N\) 以下であるとき答えに \(1\) を加算する。
• \(p^8\) が \(N\) 以下であるときにも答えに\(1\)を加算する。ただし、オーバーフローに注意。

実装は以下のようになります。 なお、エラトステネスの篩は定期的に使用機会のあるアルゴリズムなので、ライブラリ化しておくとよいでしょう。（以下をコピペしても大丈夫です）

#include<bits/stdc++.h>
using namespace std;
//この問題で扱う整数は最大4×10^12であり、int型の上限を超えるため、long longを用いる。
//実装の簡略化のためlong longをllとして使えるようにする。（以下、llという型はlong long型と同じ）
using ll = long long;

//コピペする場合はここから～
//Era(n)を呼んだ後、isprime[i]=iが素数かどうか　となっている。
vector < bool > isprime;
//返り値は素数のリスト。
vector < ll > Era(int n) {
	isprime.resize(n, true);
	vector < ll > res;
	isprime[0] = false;
	isprime[1] = false;
	for(ll i = 2; i < n; ++i) isprime[i] = true;
	for(ll i = 2; i < n; ++i) {
		if(isprime[i]) {
			res.push_back(i);
			for(ll j = i * 2; j < n; j += i) isprime[j] = false;
		}
	}
	return res;
}
//コピペする場合は～ここまで

int main(){
	ll n;
	cin >> n;
	vector<ll> v = Era(1000005);
	ll ans{};
	for(ll p:v){
		if(p*p*p*p>n)break;
		//オーバーフロー対策
		if(p<100){
			//pow関数は誤差が出ることに注意。8乗程度ならこうやって書いた方が安全（ただし数え間違いの危険はある）
			if(p*p*p*p*p*p*p*p<=n)ans++;
		}
		for(ll q:v){
			if(q<=p)continue;
			if(p*p*q*q<=n){
				ans++;
			}
			else{
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

提出コード(8ms)