\(a,b,c\) の値として考慮すべき値はすべて \(\sqrt{N}\) 以下です。特に、 \(ac\) の値は \(\sqrt{N}\) 以下です。

\((ac)^2 \leq N\) を満たす \((a,c)\) の組を探索し、 \(a\lt b\lt c\) かつ \(b \leq N/(ac)^2\) を満たす素数 \(b\) がいくつあるか求められればよいです。 \((a,c)\) が組として異なるとき \(ac\) の値は一致しないので、探索すべき組 \((a,c)\) の個数は \(\sqrt{N}\) 以下です。 \(a\) も \(c\) も素数の小さい順に探索すると、必要な組の列挙は \(O(\sqrt{N})\) 時間です。

素数を数えるときは列挙した素数の列を二分探索します。計算量は \(\tilde{O}(\sqrt{N})\) （ \(\log N\) がいくつ掛かるかは無視する）です。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const long long Z = 1000000;
bool isprime[Z+1] = {};
int count_primes[Z+1] = {};
vector<long long> primes;


int main(){
    for(int p=2; p<=Z; p++) isprime[p] = true;
    for(int p=2; p*p<=Z; p++) if(isprime[p]){
        for(int q=p*p; q<=Z; q+=p) isprime[q] = false;
    }
    for(int p=2; p<=Z; p++) if(isprime[p]){
        primes.push_back(p);
        count_primes[p] = 1;
    }
    for(int p=2; p<=Z; p++) count_primes[p] += count_primes[p-1];

    long long N; cin >> N;
    long long ans = 0;
    for(long long a=2; a*a*a*a*a<=N; a++) if(isprime[a]) {
        for(long long c=a+1; a*a*a*c*c<=N; c++) if(isprime[c]) {
            long long br = min(c-1, N/(a*a*c*c));
            long long bl = a;
            if(bl < br) {
                ans += count_primes[br];
                ans -= count_primes[bl];
            }
        }
    }
    cout << ans << endl;
    return 0;
}