エラトステネスのふるい

Math Python

エラトステネスのふるいとは、素数を列挙する簡単な方法です。
偶数の素数は2だけなので3以上の奇数だけを調べれば良いですね。

flag[i]は2i + 3が素数かどうかを表します。（i = 0,・・・N）
N = 8190なら2 × N + 3 = 16383まで調べるので1900番目の素数16381までが見つかります。

>>> N = 8190
>>> def eratosthenes():
	count = 1
	#print ("%8d") % 2,
	flag = [1 for i in range(N + 1)]
	for i in range(N):
		if(flag[i]):
			p = 2 * i + 3
			#print ("%8d") % p,
			for k in range(i + p, N, p):
				flag[k] = 0
			count += 1
	print ("count = %d") % (count)
>>> 
>>> eratosthenes()
count = 1900

CやJavaでは下記のようなforループは見慣れていますが、

for(k = i + p; k <= N; k += p)

これをPythonで書くと次のようになります。第一引数が開始位置、第二引数が終了位置、第三引数が増加分となるようです。

for k in range(i + p, N, p):