\(a,c\)が\(2\)乗なので,範囲が小さい. よって,\(a,c\)を先に全探索した方が楽. \begin{align*} for \ a, c & \\ & for \ b \end{align*} の形.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// エラトステネスの篩
template<typename T>
isPrime[0] = false;
isPrime[1] = false;
for (T i = 2; i <= n; i++ )
{
if ( !isPrime[i] ) continue;
T a = 2*i; // i の倍数
while( a <= n ){
isPrime[a] = false;
a += i;
}
}
return isPrime;
}
int main() {
ll n; cin >> n;
ll m = 1e6;
vll vec;
srep(i,2,m) if(vp[i]) vec.push_back(i); //sp.insert(i);
ll ans = 0;
set<ll> st;
rep(ai,vec.size()){
ll a = vec[ai];
if(a*a*a*a*a > n) break;
srep(ci, ai+2, vec.size()) {
ll c = vec[ci];
if(c*c*a*a*3 > n) break;
srep(bi, ai+1, ci) {
ll b = vec[bi];
ll x = a*a*b*c*c;
if(x > n) {
break;
}else{
st.insert(x);
}
}
}
}
cout << st.size() << endl;
return 0;
}