採用しているアルゴリズムに問題があると思います。なので素数判定のアルゴリズムについて検索することをおすすめします。
N以下の素数をすべて列挙するアルゴリズムでO(N)に近い時間計算量を持つものが知られています。ただし、この問題に関してはデータセットが30まであるので、もうひと工夫必要だと思われます。
注意:以下ネタバレになります
エラトステネスのふるいというアルゴリズムを使えば、N以下の素数をO(N*log(log(N)))の時間で列挙することができます。これは簡単に言えば、数を小さい方から見ていって、その数の倍数に「素数でない」印をつけていくというものです。
コードは次のようなものが考えられます。
(以下のコードは本番で試したわけではないので、何か問題があればレスポンスをください)
import sys
N = 10**6
is_prime = [True for _ in range(N)]
c = 0
count = [0 for _ in range(N)]
# sieve
p = 0
is_prime[0] = is_prime[1] = False
for i in range(2,N):
if is_prime[i]:
c += 1
for j in range(i*2*i, N, i):
is_prime[j] = False
count[i] = c
for line in sys.stdin:
print(count[int(line)])