[Python]エラトステネスのふるいで素数を求める

C#で書いたものをPythonで書いてみた

昨日のエントリで書いたC#のコードを、Pythonだとどうなるか書き換えてみた。

Pythonのコード

※ 2018/4/24修正
変数名「dict」を「dic」に修正。(「dict」は組み込み関数名なので、変数名として適切でない)

fr = 1
to = 200

# ディクショナリ初期化
# keyは整数、
# valueはステータス(0：判定前、1:消した(素数でない)、2:○をつけた(素数))
dic = {}
for i in range(1, to + 1):
    dic[i] = 0

# 単数の1を消す   
dic[1] = 1

prime_number = 2

# 素数の2乗が範囲内のところまでループ
while prime_number * prime_number < to:
    # 未判定の最小値を素数とする
    prime_number = min([item[0] for item in dic.items() if item[1] == 0])
    # ○をつけた(2を立てる)
    dic[prime_number] = 2

    # 未判定の値のうち、素数の倍数のリスト取得
    target_numbers = [item[0] for item in dic.items() if item[1] == 0 and item[0] % prime_number == 0]
    for n in target_numbers:
        # 合成数として消す(1を立てる)
        dic[n] = 1

# 残った値は全部素数として○をつける(2を立てる)
remain_numbers = [item[0] for item in dic.items() if item[1] == 0]
for n in remain_numbers:
    dic[n] = 2

# 素数と判定された値を出力
prime_numbers = [item[0] for item in dic.items() if item[1] == 2]
print (prime_numbers)

出力結果

以下の通り出力。OK！

C#でLinq to Object使いまくりだったので、
Pythonだとめんどくさいかも？と思ったけど、そうでもなかった。
リスト内包表記がすごく便利でした。