【ちょっとづつAtCode】ABC193　C – Unexpressed

引用

（引用）

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

AtCoder Beginner Contest 193　C – Unexpressedより引用

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 １

8

出力例 １

6

4,8 は 2^2=4, 2^3=8 と、a^b の形で表すことができます。
1,2,3,5,6,7 は 2 以上の整数 a,b を用いて a^b と表せないので、答えは 6 です。

a^bで表せる方が少ないとはすぐに気づくのですが、2^4と8^2で重複してしまうから素数を羅列〜とか色々考えてしまったのですが、セットで重複を消せば良かったんですね

N ＝　６５として

from decimal import Decimal as De
N = int(input())
n = De(N)
A = {0}
for i in range(2, int(n.sqrt()+1)):
    x = 0
    j = 2
    while x <= n:
        x = i ** j
        if x <= n:
            A.add(x)
            j += 1
print(N - len(A) + 1)

from decimal import Decimal as Deはいらないかもしれないけれど、なんとなくつけました。

解説のやつがめちゃシンプル

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))

空集合へ追加できないから

A = {}
A.add(何か)ってやると、エラーが出るので（敢えて{0}を入れてた）
A = set()ってやるんですね