見出し画像

エラスネスの篩による素数の計算

ギリシャの数学者、エラトステネスが考案した素数の選別法で、正の整数を小さい順に並べ、まず1を消去し、次に2、3、5…と小さい方の素数を残してそれらの倍数を消去することで、最終的に残ったものが素数であるあとする方法です。

そこで、Pythonでエラスネスの篩を使い素数のリストを作ります。いろいろな方法がありますが、NumPyを使う方法が最も面白いと思われます。

エラスネスの篩による素数の計算

NumPyモジュールを使うともっとスマートに計算することができます。ここではndarray形式で計算対象とする数を要素とするリストis_primeを定義し、とりあえず、すべてが素数であると仮定してTrueをセットしておき、約数を持つなど素数でないと判断したときにはFalseをセットする方法を採ります。

import numpy as np
num=100
is_prime = np.ones((num,), dtype=bool)
is_prime[:2] = False
for j in range(2, int(np.sqrt(num))+1):
   is_prime[2*j::j] = False
prime=list(np.arange(num)[is_prime])
print(prime,len(prime))

#[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] 25

1以上100以下の整数の中で素数が25個であることがわかります。

3. ndarray形式で計算対象とする数を要素とするリストis_primeを定義し、仮に素数でないという意味を込めてFalseをセットしておきます。なお、リストの要素数は0からnumまでのnum+1個になります。
4. 0,1は素数ではないのでFalseをセットします。
5. 2からnumの平方根までの整数jについて、jの2倍、3倍、4倍・・・とリストの最後までのjの倍数は素数ではないと判断して、Falseをセットします。
7.  is_prime の中でTrueがセットされている要素の整数が、リストprimeに代入されます。この機能をNumPyのブロードキャスト機能といいます。

ある範囲の整数について、各整数それぞれについて2から自身の平方根までの整数で順次割り返していき、割り切れたら素数ではない、というような判断をする必要があるのでかなり大変です。今度どれくらい効率的になったのか試してみたいと思います。


この記事が気に入ったらサポートをしてみませんか?