どん底から這い上がるまでの記録

どん底から這い上がりたいけど這い上がれない人がいろいろ書くブログ(主にプログラミング)

エラトステネスの篩

スポンサーリンク


エラトステネスの篩(ふるい)とは、

ある整数n以下の全ての素数を見つけるための高速なアルゴリズムのこと。

アルゴリズム

  1. 2からnまでの整数をリストに入れる。
  2. 2から順番にその倍数(その数自身は除く)をリストから削除していく。
  3. nの平方根になれば終了。リストに残ったものが素数となる。

(例)n=12

1. 2から12までの整数を用意。

 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

2. 2から順番にその倍数(その数自身は除く)を削除していく。

 ①2の倍数をリストから削除

 [2, 3, 5, 7, 9, 11]

 ②3の倍数をリストから削除

 [2, 3, 5, 7, 11]

3. 12の平方根に達したので終了。

n=12以下の素数として[2, 3, 5, 7, 11]を得ることができた。

プログラム

pythonでのプログラムを書いてみる。

n = 12
# 1. 2から12までの整数を用意。
# ここでは長さ13のリストを用意し、インデックスが整数に対応している。
# 例えば、整数2はprimes[2]。
# リストの中身は素数ならば1、削除されれば0とする。
# つまり、2から12までののリストを用意すると次のようになる。
# [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
primes = [0, 0] + [1] * (n-1)

# 平方根
root = int(pow(12, 0.5))+1
# 2. 2から順番にその倍数を削除していく。
# ここでの削除は値を0にすることである。
for i in range(2, root):
    if primes[i]:
        for j in range(i*i, n+1, i):
            primes[j] = 0

print(primes)
# [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0]

primes = [i for i in range(n+1) if primes[i]]
print(primes)
# [2, 3, 5, 7, 11]