pythonで「エラトステネスの篩」を書く

目的：簡単なアルゴリズムを徹底的に追求する予定で、とりあえず作ったもの。だから今後改良版を作っていく予定。「追求」っていのうはコメントの書き方、コードの書き方、計算の仕方を「うまい具合」にしていくってこと。

# coding: utf-8
# エラトステネスの篩
# 指定された整数以下の全ての素数を発見するための単純なアルゴリズム
# https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

import math

# 整数指定
Nini = int(input())

# 探索リスト
Search_list = range(2,Nini+1)

# Search_list上で素数以外を先頭から－1にするループ
# headに先頭値を設定
# headで割り切れるものを-1に設定
# 最後に-1ではないものが素数
for i in xrange(0,Nini-2):
	if Search_list[i] != -1:
		head = Search_list[i]
	elif Search_list[i] == -1:
		continue
	for j in xrange(0,Nini-1):
		if Search_list[j] == head:
			continue
		elif Search_list[j] % head == 0:
			Search_list[j] = -1
	if head > math.sqrt(Nini):
		break

# Search_list上の-1以外をansに追加
ans = []
for x in xrange(0,Nini-1):
	if Search_list[x]!=-1:
		ans.append(Search_list[x])
print ans