AtCoder Beginner Contest 193 C問題

AtCoderを始めましたが、ABCのA・B問題はほぼ解ける、C問題は運が良ければ解けるというレベルです。
まずはC問題を難なく解けるというの目標に、まずは過去問のC問題までをどんどんやっていってます。

自力では解けなかった問題を、解説を見て、理解した内容の整理とその結果のコードを書いていきたいと思います。

問題

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

解けなかった原因

問題文を素直に説こうとすると、２〜Nまで総当たりで試して数えていくことになるが、計算量が多すぎてTLEになってしまう。

解き方

・表せないものよりも表せるものの方が数が圧倒的に少ないので、表せるもの一覧を作り、Nから一覧の個数を引いて答えを出すようにする。
・累乗なので、Nまで試行する必要はなく、Nの平方根までで十分。
・$2^4=16$と$4^2=16$など別の組み合わせで同じ数になることを考慮する。

ACしたコード

import math

N = int(input())
end = math.ceil(math.sqrt(N))+1

l = {}
for i in range(2,end) :
    for j in range(2,end) :
        n = i**j
        if n > N :
            break;
        l[n] = 1

print(N-len(l))