少し力づくな解法をしてみましょう。
サンプル2 から読み取れる通り、条件を満たす整数として考えるべきは 1001003332 個です。 また、 \((10^9)^2 = 10^{18}\) なので、このうち \(10^9\) 個は \(a^2\) の形で表現できます。

よって、 \(a^2\) の形で表現できない条件を満たす整数は \(10^6\) 個程度しかありません。なので、これらを予め全列挙した上で \(a^2\) の形で表現できる整数の個数を足すことでこの問題に正解できます。

この全列挙は \(b=3,4,\dots,59\) に対して行ったうえで \(a^b > N\) となった時点で打ち切ればよく、ある整数 \(x\) が \(a^2\) の形で表現できるかの判定は \(( \lfloor \sqrt{x} \rfloor )^2=x\) かどうかで判定すればよいです。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

long long safe_pow(long long a,long long b){
  long long res=1;
  for(long long i=0;i<b;i++){
    double dres=res;
    dres*=a;
    if(dres>2e18){return 2e18;}
    res*=a;
  }
  return res;
}

long long sqrt_floor(long long x){
  long long l=0,r=2e9;
  while(l<=r){
    long long t=(l+r)/2;
    if(t*t>x){r=t-1;}
    else{l=t+1;}
  }
  return r;
}

int main(){
  long long n;
  cin >> n;
  set<long long> st;
  for(long long b=3;b<60;b++){
    for(long long a=2;;a++){
      long long x=safe_pow(a,b);
      if(x>n){break;}
      long long s=sqrt_floor(x);
      if(s*s!=x){st.insert(x);}
    }
  }
  long long res=st.size();
  res+=sqrt_floor(n);
  cout << res << "\n";
  return 0;
}