Published on

Pythonでエラトステネスの篩を使って素数を抽出する

Authors

素数を抽出するアルゴリズムであるエラトステネスの篩(ふるい)は、紀元前275年から194年のギリシャの学者であるエラトステネスによって発明されたアルゴリズムです。

実際のアルゴリズム

1.100個の配列を準備(100までの数で素数を求める場合) 2.すべての配列の中身に1を代入 3.2の倍数番目の中に0を代入 4.3の倍数番目の中に0を代入 5.4番目はすでに0なので、次に進む 6.5の倍数番目の中に0を代入 7.6番目はすでに0なので、次に進む 100の平方根まで繰り返す . . . 最後まで1が代入されていた配列番号が素数です。

Pythonでエラトステネスをコーディング

s = []
#配列の初期化
for _ in range(2):#0と1は除外する
    s.append(0)
    for _ in range(99):#2以降の配列番号に1を代入
    s.append(1)

#素数検索
i = 2
while i*i <= 100:
  j = 2

while i*j <= 100 and s[i] != 0:
  s[i*j] = 0
  j += 1

  i += 1

#表示
i = 2
while i <= 100:
  if s[i] == 1:#1が代入されている配列番号が素数
    print i,
    i += 1