CodeIQ：素数の数を教えてください

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「素数の数を教えてください」（CodeIQ）を参照してください。

問題の概要

標準入力から1行に1つずつ、複数行の数値が与えられます。
入力された数値未満の素数がいくつあるかを出力してください。
テストケースは2つあり、1つは上限1000、2つ目は上限100000です。

【入力】

5
10

【出力】

2
4

私のプログラム

Pythonで解答しています。

#!/usr/local/bin/python3
# -*- coding:utf-8 -*-

import fileinput
import math
import re

# 素数かどうかを判定する
def isPrime(n, p):
	for i in p:
		if i > math.sqrt(n):
			break
		if n % i == 0:
			return False
	return True

if __name__ == "__main__":
	Prime = []
	n = 0
	m = 2
	for line in fileinput.input():
		if not line.strip():
			continue

		line = line.strip()
		n = int(line)

		for i in range(m,n):
			if isPrime(i, Prime):	Prime.append(i)

		m = n

		print(str(len(Prime)))

解説

素数を数えること自体は難しくありません。
問題は1回のテストケースに複数の入力があるということで、毎回数え直していたら時間切れになります。

素数判定

有名でまずまず高速な素数判定方法に「エラトステネスの篩」があります。ですが私はもっと単純（だけれども遅い）方法で解答しています。理由は複数の入力があるため続きから計算したかったためです。
実は提出した後で、「エラトステネスの篩」を使ってやる方法を思いつきました…。一度、入力を全部読んでその中の最大値に対して「エラトステネスの篩」で素数をリストアップし、入力値以下の要素数を返せばよかったわけです。

一応、ロジックを説明します。
Primeは素数のリストです。
isPrime(n,p)はnがチェック対象の値、pは既知の素数のリストです。nをpに存在する値で順次割ってみていずれの値での割れなかったら素数とする素朴な関数です。
mainの81行目のループはmが前回の最後の値、nが今回の値なので例のような入力だと1回目で2〜4、2回目は5〜9をチェックすることになり無駄がありません。

雑感

この問題自体は関係ありませんが、ふとPythonはCに比べてどのくらいの性能だろうと思い、C言語でもやってみました。するとC言語の方が約17.5倍速いと言う結果になりました。
この情報は他の問題をやるときに時々役に立っていて、Pythonで時間切れになった時に真面目にアルゴリズムを考え直すか、言語を変えてクリアしてしまうかの判断基準になっていたりします。