【記事の目標】
0から任意の数値（ｎ）までの素数を抽出する。
【作業手順】
１．エラトステネスの篩のロジックを組んでみよう
２．任意の数値までの素数を抽出してみよう
１．エラトステネスの篩のロジックを組んでみよう
素数を見つけたい、そんなときは「エラトステネスの篩」ですね。
まずは、任意の数値までの配列を用意して、先頭にFALSEを、以降にTRUEを設定します。
今回の場合は配列は 0 番目から作成されるため、2番目の要素である1までFALSEを設定します。
prime_list = [False, False] + [True]*(n-1)
任意の数字（ｎ）を 8 にしてみましょう。
するとこのリストは以下のように作成されます。
[False, False, True, True, True, True, True, True, True]
要素は9個ありますが、一番最初が 0 番目の要素であるため、
0,1,2,3,4,5,6,7,8の9要素となっています。
次に、どの数まで繰り返し調べるかを算出します。
任意の数字（ｎ）の平方根（ルート）の小数点以下を切り捨てした整数の値に 1 を加算した数まで調べます。
target = math.floor(math.sqrt(n)) + 1
任意の数字（ｎ）を 8 とすると、
math.sqrt(n) は 2.8284271247461903
math.floor(math.sqrt(n)) は 2
math.floor(math.sqrt(n)) + 1 は 3
となります。
これで繰り返し処理をさせる最大の数字は 3 となりました。
ここで注意です、0 と 1 はすでにFALSE（素数ではない）ため、以降の処理は 2 から算出した最大の数字まで処理します。
では繰り返し処理を書いていきましょう。
for i in range(2, target):
i は 2 から target （今回の場合は 3 ）まで繰り返します。
処理の先頭で、すでにFALSE判定されているものはスキップするようにしましょう。
if not prime_list[i]:
continue
素数でないと判断するために、2 から最大の数（今回の場合は 3 ）まで 2 倍した数にFALSEを入れていきます。
for j in range(i * 2, n + 1, i):
prime_list[j] = False
今回は任意の数字（ｎ）を 8 としているため、このロジックでは以下のように数字にFALSEを入れていきます。
i = 2 のループ処理
1 回目：j = 4 であるため、4 にFALSEを設定
2 回目：j = 6 であるため、6 にFALSEを設定
3 回目：j = 8 であるため、8 にFALSEを設定
i = 3 のループ処理
1 回目：j = 6 であり、すでにFALSE設定されているため、処理スキップ
処理終了
この通り、4, 6, 8 にFALSEが設定されました。
処理後のリストは以下のようになります。
[False, False, True, True, False, True, False, True, False]
ここでTRUEになっている要素の数字を取り出すと、素数の一覧になりますね。
result_list = []
for i in range(n + 1):
if l[i]:
result_list.append(i)
これで、 result_list を出力すると、
[2, 3, 5, 7]
となり、 8 までの素数を抽出できましたね。
２．任意の数値までの素数を抽出してみよう
先ほどのロジックを関数にして呼び出してみましょう。
def eratosthenes(n):
prime_list = [False, False] + [True] * (n - 1)
target = math.floor(math.sqrt(n)) + 1
for i in range(2, target):
if not prime_list[i]:
continue
for j in range(i * 2, n + 1, i):
prime_list[j] = False
return prime_list
n = 8
l = eratosthenes(n)
result_list = []
for i in range(n + 1):
if l[i]:
result_list.append(i)
では n = 11 にして動かしてみましょう。
結果予想では、先ほどの 8 で実施した結果に 11 が追加されているイメージですね。
以下、実行結果です。
[2, 3, 5, 7, 11]
予想通り、任意の数字（ｎ）までの素数が取得できましたね。
忙しくて久しぶりの記事投稿になりました。
急に素因数分解がしたくなって、ロジックを組んで遊んでいたので、遊んでいました。
こういった数学の処理をロジックに起こしてみるのも、ロジックを書く練習になると思いますので、試しにやってみても良いかもですね。
