\(N ≤ 10^{10}\) であるので、\(1\) から \(N\) までの整数をそれぞれ判定することができません。
そこで、\(a^b\) と表せる整数が非常に少ないことに注目します。
\(2\) 以上の整数の組 \((a, b)\) であって、\(a^b ≤ N\) であるものは、

\[ \sum_{x=2}^{\lfloor\log_2N\rfloor}(\lfloor\sqrt[x]{N}\rfloor - 1) ≤ 102719 \]

個なので、\(a^b ≤ N\) の範囲で \(a, b\) を全探索し、\(a^b\) と表せるものを HashSet で管理することで十分高速にこの問題を解くことができます。

回答例 (C++)

#include <iostream>
#include <unordered_set>
using namespace std;
using ll = int64_t;

int main(){
    ll N;
    cin >> N;
    unordered_set<ll> s;
    for(ll a = 2; a * a <= N; a++){
        ll x = a * a;
        while(x <= N){
            s.insert(x);
            x *= a;
        }
    }
    cout << N - s.size() << endl;
}

回答例 (Python)

N = int(input())
sq = int(N ** 0.5)
s = set()
for a in range(2, sq + 1):
    x = a * a
    while x <= N:
        s.add(x)
        x *= a
print(N - len(s))