再帰的に素数を求める

はじめに

　Python学習の一環として、素数を再帰的に求めるコードを作成しました。

コード

　今回はエラトステネスの篩を用いました。

エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。
（Wikipedia「エラトステネスの篩」より引用）

　以下がコードです。

Sieve.py

array = [i for i in range(2, 100)]  #求めたい値の範囲  
prime = [2]                  #素数のリスト

def Sieve(array, prime):     #エラトステネスの篩
  newArray = []
  for i in array:
    if i%prime[-1] != 0:
      newArray.append(i)
  prime.append(newArray[0])  #リストに素数を追加
  if array[-1] == prime[-1]:
    return prime             #素数のリストを返す
  return Sieve(newArray, prime)

Prime = Sieve(array, prime)
print(Prime) #出力

　結果、2から100 99までにある素数が求まりました（2019年12月22日訂正）。

出力

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

おわりに

　Pythonで再帰を扱うときは上限があるそうですね。上限と変更方法がこちらの記事で解説されていました。

　ご覧いただきありがとうございました。ご指摘等ありましたらコメント欄にお願いします。