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

Pythonで素数を計算するためには次の通り1つ1つの整数を、自身の平方根までで割り返して、全て割り切れない（%演算子で計算して余りが0にならない）場合に、素数とする方法が最も単純です。

素数を地道に計算する
  1. prime = []
  2. max = 100
  3. for i in range (2,max +1 ):
  4. for j in range(2, int(i**0.5 ) + 1):
  5. if i % j ==0:
  6. break
  7. else:
  8. prime.append(i)
  9. 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

ここでは、リストprimeに素数が追加されていきます。2以上100未満までの間に25個の素数があることがわかります。

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

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

リストによる方法

2からnまでの整数（1は素数でないのではじめから除外）を要素とするリストprimeを定義し、2からnの平方根までの整数に対し倍数となるものを消去します。ここで割る数は素数だけを選べばよいのですが、その判断が大変なので合成数も含めることとします。

エラスネスの篩による計算
  1. n=100
  2. prime=list(range(2,n+1))
  3. prime
  4. for i in range(2,int(n**0.5)+1):
  5. for j in range(2,int(n/i)+1):
  6. if i*j in prime:
  7. prime.remove(i*j)
  8. 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
6.　候補となる数値がリストにあれば、removeメソッドで消去します。
結果は前節と同じです。

NumPyによる方法

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

NumPyのブロードキャスト機能を使い素数の一覧を作成
  1. import numpy as np
  2. num=100
  3. is_prime = np.ones((num,), dtype=bool)
  4. is_prime[:2] = False
  5. for j in range(2, int(np.sqrt(num))+1):
  6. is_prime[2*j::j] = False
  7. prime=list(np.arange(num)[is_prime])
  8. 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
3.　ndarray形式で計算対象とする数を要素とするリストis_primeを定義し、仮に素数でないという意味を込めてFalseをセットしておきます。なお、リストの要素数は0からnumまでのnum+1個になります。
4.　0,1は素数ではないのでFalseをセットします。
5.　2からnumの平方根までの整数jについて、jの2倍からjをきの数は素数ではないと判断して、Falseをセットします。
7.　 is_prime の中でTrueがセットされている要素の整数が、リストprimeに代入されます。この機能をNumPｙのブロードキャスト機能といいます。

SymPy. sieveによる方法

SymPyにはprimerange関数を使いある範囲の素数をリストにすることができますが、SymPy.sieveを使うとエラスネスの篩を使い計算するようにできます。

SymPy.sieveを使い素数のリストを作成する
  1. import sympy
  2. prime=list(sympy.sieve.primerange(1, 100))
  3. 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