ほぼ日刊競プロ ABC193 C - Unexpressed

C - Unexpressed

問題文
整数 N が与えられます。 1 以上 N 以下の整数のうち、 2 以上の整数 a,b を用いて a^bと表せないものはいくつあるでしょうか？

考えたこと

制約上Nの最大値は10^10なので２以上の整数aは2から10^5の範囲，bは2から多く見積もっても100で確かめればよい．
setを用いてハッシュテーブルで数を追加していく．

N=int(input())
temp = set()
for a in range(2,(10**5+10)):
   for b in range(2,100):
       if a**b<=N:
           temp.add(a**b)
       else:
           break
print (N-len(temp))