AIZU ONLINE JUDGEの0009で何回やってもTime Limit Exceedと表示されます。

久々にやったAIZU ONLINE JUDGEのこの問題で困ったことが起こったので、質問させていただきます。

問題を解くコードをPython3で書いたのですが、何回やってもTime Limit Exceedと表示されます。証拠となるソリューションはこのリンクにあります。

何が原因で、その解決方法はないのでしょうか？
わかる方、いましたら教えてください。

なお、コードは以下のとおりです。

import sys

def prime_calc(n):
    if n < 2:
        return False
    else:
        i = 2
        while n > i:
            if n % i == 0:
                return False
            else:
                i += 1
    return True

def prime(n):
    cnt = 0
    for i in range(0, n+1):
        ans = prime_calc(i)
        if ans is True:
            cnt = cnt + 1
    return cnt

def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime(line))

if __name__ == "__main__":
    main()

追記:
Fumu 7さんの解法を使ったのですが、それでもTime Limit Exceededと表示され、入力例を試しても、正しい数値にならず以下のような数値になってしまいます。

9
2
10

一体、何が原因なんでしょうか？

ちなみに、Fumu7さんの解法を使ったコードは以下のとおりです。

import math
import sys

def prime_calc(n):
    if n < 2:
        return False
    elif n==2 or n==3 or n==5 or n==7:
        return True
    else:
        rootN = math.floor(math.sqrt(n))
        i = 11
        while rootN > i:
            if n % i == 0:
                return False
            else:
                i += 2

    return True

def prime(n):
    cnt = 0
    for i in range(2, n+1):
        ans = prime_calc(i)
        if ans is True:
            cnt = cnt + 1

    return cnt

def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime(line))

if __name__ == "__main__":
    main()