AtCoderを始めましたが、ABCのA・B問題はほぼ解ける、C問題は運が良ければ解けるというレベルです。
まずはC問題を難なく解けるというの目標に、まずは過去問のC問題までをどんどんやっていってます。
自力では解けなかった問題を、解説を見て、理解した内容の整理とその結果のコードを書いていきたいと思います。
#問題
整数 N が与えられます。 1 以上 N 以下の整数のうち、 2 以上の整数 a,b を用いて $a^b$ と表せないものはいくつあるでしょうか?
#解けなかった原因
問題文を素直に説こうとすると、2〜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))