idが素数かどうか判定するスクリプト

なんか、

あなたのmixiのidは素数ですか？

なんて話があったので、ちょっと作ってみました。
使い方：

>python pure_number.py 3
2
3
id is pure number: 3
0.0 sec

>python pure_number.py 91
2
3
5
...
89
97
id is not pure number: 91
0.0160000324249 sec

pure_number.py

#!/usr/bin/python
# -*- coding: sjis -*-
import time

pureList = []


def calc(i,j):
	if i % j == 0: return False
	return True

def is_pure_number(id):		
	t = time.time()

	i = 2
	while len(pureList) < 1000000:
		if len(pureList) > 0:
			n = int(pureList[-1])
			if  n > id:
				print "id is not pure number:",
				print id
				break
			
		flag = True
		for j in pureList:
			if i < j*j:
				break
			if calc(i,j) == False:
				flag = False
				break
		if flag == True:
			pureList.append(i)
			print i
			if i == id:
				print "id is pure number:",
				print id
				break
			
		if(i == 2): i = 3
		else: i += 2
	print time.time() - t ,"sec"

if __name__ == "__main__":
	import sys
	if len(sys.argv) != 2:
		print "usage python pure_number.py id"
	else:
		id = sys.argv[1]
		is_pure_number(int(id))

注意点

アルゴリズムがヘタレなんで、でかい数値を入れるとそれなりに時間かかります。
試しに1300万と1なんてやってみたら、267secなんてかかりました(Core2Duo E6600,XPSP2,CPython2.5。IronPython1.1なら約160sec)