読者です 読者をやめる 読者になる 読者になる

凡庸なる人のブログ

凡庸な自分が思ったことや何かしらの感想、コンピュータ系などの調べごとを書くブログです。  【結論】ってのは私個人の結論です。記事全体は個人的な調査結果や感想です。

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