Pythonで素数の計算をする

数学の中でも素数は非常に面白いテーマです。その面白さを味わうための準備としていろいろな素数にかかわるいろいろな関数を作成します。これらの機能は、SymPyモジュールに関数が用意されていますが、自分で作ることができるようになると、応用範囲がより広がります。

Pythonにより100までの素数を求める

素数の一覧を出力するプログラム

2以上ある自然数未満の素数を求めるプログラムを作成します。ここでは変数limit=100として、100未満の素数を出力します。

100未満の素数を列記する

limit = 100
for i in range(2, limit):
for j in range(2, i):
if i % j == 0:
break
else:
print(i, end=' ')

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

2.　iを素数の候補とし、2からfor文でループして素数であるかを調べます。2からとしているのは、1が素数でないためです。また、range関数は2番目の引数より1つ手前で処理を終えてしまうので、limit=100とすると100未満、つまり99まで調べることになります。「未満」ではなく「以下」としたい場合はlimit+1とします。

3.　jを約数の候補として、2から素数の候補であるiを順次割り算をしていきます。range(2.limit)については、後でもっと効率よくする方法を検討します。

4.　ここであるjで割り切れる、つまり余りが0になったら、そのiは素数ではないので5.でbreakし次のiを素数であるか判定します。

6.　iが素数であるときは、割ることができるjが存在しないので3.のforループから抜け、else節に入りその数を出力します。

7.　print(i)とすると縦に表示されてしまうので、end=” ”とすることで横に並べて表示します。

素数の一覧をリストにする

応用的な問題を考えるときに、ある範囲の素数をリストにしておくと便利です。このプログラムは、#1を少し変更するだけで簡単に作成することができます。3行目でprimeというリストを定義し、素数である場合#1の6行目にあるprint文の代わりにprimeに追加していきます。

100未満の素数をリストにする

def prime(limit):
prime = []
for i in range(2,limit):
for j in range(2, int(limit**0.5)+1):
if i % j == 0:
break
else:
prime.append(i)
return prime
prime(80)

[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79]

2.　計算した素数をリストとして返すため、primeというリストを定義します。

4.　for文の2番目の引数をlimitではなくint(limit**0.5)+1と変更します。なぜなら、例えば36の約数を考えると、積が36になるような組み合わせは (1,36)、(2,18) 、(3,12) 、(4,9)、(6,6)となります。このことから、素数ではない場合、2からlimitの平方根までの間に必ず約数が存在するので、その間に約数がなければ素数と判断できるためです。またint関数を使うのは、平方根が整数にならないとfor文がエラーになるので、切り捨てて整数にそろえるためです。

8.9. 約数が見つからず素数として判断されるとprimeに使いされ、プログラムの最後で戻り値として返されます。

10行目でリストprimeを出力して、結果を確認することができます。

素数であるかを判定する

素数であるかを判定する関数

素数の定義に従ったプログラム

ある自然数numが与えられたとき、その数が素数であればTrue、素数でない場合はFalseを返すプログラムを作成します。例えば、num=36としてプログラムを実行すると、36は約数を持つ合成数で、素数ではないのでFalseを出力します。

素数であるか判定する

num = 36
if num <= 1:
print(False)
else:
for i in range(2, int(num**0.5)+1):
if num % i == 0:
print(False)
break
else:
print(True)

False

2.　0や負数は素数ではないので、numが1以下であればFalseを出力します。

4.　1でない場合に5行目のelseに入ります。ここで6行目のfor文以下、約数の候補をiとして順次numを割り算します。余りが0になれば、Falseと表示してbreak文でforループから抜けプログラムは終了します。

9.　for文でnumを割って余りが0になる数がない場合は素数となり、10行目のelse節に入り、Trueつまり素数と判断します。

フラグを使って少しだけすっきりとしたプログラム

#3と同じ考え方ですが、変数flgというフラグを使う方法をご紹介します。

そもそも素数という観点で整数を見ると、素数でない1以下と、2以上の素数、および1と自身以外の約数を持つ合成数の3つに分類されます。ということは、はじめにflgにFalseをセットしておき、forループの結果、約数が存在し素数と判断されたとだけflgにTrueをセットし、最後にflgの値を出力すれば結果は同じになります。num=36として実行した場合、約数2が見つかった時点でforループから抜けてflgにFalseがセットされます。

フラグを使って素数であるか判定する

num = 36
flg = False
for i in range(2, int(num**0.5)+1):
if num % i == 0:
break
else:
flg = True
print(flg)

False

素数かどうかを判断するプログラムを関数にする

is_primeという関数を定義し、#3のプログラムと同じ考え方で素数かどうかを判定して返すようにします。

素数かどうかを判定する関数

def is_prime(i):
if i <= 1:
return False
for j in range(2, int(i**0.5) + 1):
if i % j == 0:
return False
return True
print('1は素数？',is_prime(1))
print('2は素数？',is_prime(2))
print('8は素数？',is_prime(8))

1は素数？ False
2は素数？ True
8は素数？ False

関数にすると、いろいろな数字を引数に指定することにより素数か否かを判断することができます。

素数かどうかを判断する関数を活用する

前節の#5で作成した関数を使って、素数かどうかを判断する関数っていろいろな関数を作成します。関数の中でis_prime関数を使うので、あらかじめこの関数を実行しておかないとエラーになるので注意してください。

ある数値の範囲にある素数をリストで返す関数

下限（lower）以上、上限（upper）未満の範囲にある素数を求める関数を作成します。#2のプログラムと同じ考え方ですが、4行目のfor文で、lowerからupper（rangeなので-1 する）と変更するだけで、これを関数にすれば完成です。

ある範囲にある素数をリストにする関数

def prime_range(lower,upper):
prime = []
for i in range(lower, upper):
if is_prime(i):
prime.append(i)
return prime
print('1以上100未満の素数のリスト：',prime_range(1,100))
print('100以上200未満の素数のリスト：',prime_range(100,200))
print('101以上199未満の素数のリスト：',prime_range(101,199))

1以上100未満の素数のリスト： [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]
100以上200未満の素数のリスト： [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
101以上199未満の素数のリスト： [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197]

3.　for文のrangeで、変数iを素数の候補として、lowerからupper-1までループするので結果的にlower以上upper未満の間で素数か否かを判断することができます。

4.　is_prime関数を使い、iが素数かどうかを判断します。if is_prime(i)はif is_prime(i)==True:と同じ意味です。ここで素数であればリストprimeに追加します。

6.　forループを抜けると7行目でprimeを返してプログラムが終了です。

上記の通り下限（lower）以上、上限（upper）未満の範囲で素数をリストで求めることができます。

素数を小さい順番に並べてn番目の素数を求める関数

求める素数の順番をcntとして関数に引数を渡し、最小の素数2から数えてcnt番目の素数を返す関数を作成します。

小さい順に並べてcnt番目の素数を求める関数

def prime_seq(cnt):
i = 1
while 0 < cnt:
i += 1
if is_prime(i):
cnt -= 1
return i
print('1番目の素数：',prime_seq(1))
print('5番目の素数：',prime_seq(5))

1番目の素数： 2
5番目の素数： 11

2.　iを素数の候補として3行目で定義します。

3.　cnt番目の関数を求めることから、iをいくつまで調べればよいかわかりません。このような場合、4行目ではfor文に代えてwhile文を使い、素数が10個見つかるまでループを回すようにします。

4.　iに1をどんどん足しこんでいくので、2から順番に素数であるか否かを判断することになります。is_prime関数で素数と判断したときにはcntを1つ減らします。この結果、cntとして渡した数だけ素数が見つかるとcnt=0となり4行目のwhileループが終了します。このときのiはcnt番目の素数となります。

ある数を超えて小さい順にn番目の素数を求める関数

前節の#7と同じ考え方で、ある基準となる数を超えて小さい順にcnt番目の素数を求める関数を作成します。引数として、基準となる数をbase、小さい順からの順番をcntとして設定します。

ある数を超えて小さい順にcnt番目の素数を求める関数

def prime_next(base,cnt=1):
while(cnt>0):
base+=1
if is_prime(base):
cnt -=1
return base
print('100を超えて2番目の素数：',prime_next(100,2))
print('101を超えて2番目の素数：',prime_next(101,2))
print('100を超えて次の素数：',prime_next(100))

100を超えて2番目の素数： 103
101を超えて2番目の素数： 107
100を超えて次の素数： 101

3.　素数の候補として引数から渡ってきたbaseを使います。4行目でbaseに1を足しているので、引数のbase+1から素数の判定を行います。

8.9. 結果を比較すると、baseで渡した値を超えた数で計算できていることがわかります。

1.でcnt=1として関数に渡しているのは、10.の実行例のように、2番目のcntを省略すると関数は既定値（default）で1をセットしてプログラムを実行できるようにするためです。

ある数未満で大きい順にcnt番目の素数を求める関数

#8と同じ考え方で、ある基準となる数未満で小さい順にcnt番目の素数を求める関数を作成します。

ある数未満で大きい順にcnt番目の素数を求める関数

def prime_pre(base, cnt=1):
while(cnt > 0):
base -= 1
if is_prime(base):
cnt -=1
return base
print('100未満で大きい方から2番目の素数：',prime_pre(100, 2))
print('101未満で大きい方から2番目の素数：',prime_pre(100, 2))
print('100未満で最大の素数：',prime_pre(100))

100未満で大きい方から2番目の素数： 89
101未満で大きい方から2番目の素数： 89
100未満で最大の素数： 97

基準となる変数baseからはじめて、baseを素数の候補として次々と1を差し引くことにより、さかのぼって大きな数から素数を探します。

Sympyの素数に関する関数

これまで、素数に関していろいろな関数を作ってきました。なぜ、こんな関数を作るのだ！というものもありますが、sympyモジュールには同じ機能を持つ関数が用意されています。それだけ、素数は多くの分野でいろいろな使われ方をしていることを意味しています。

Sympyの素数に関する関数

import sympy
print('5は素数か？：',sympy.isprime(5))
print('-5は素数か？：',sympy.isprime(-5))
print('10番目の素数は？：',sympy.prime(10))
print('11以下の素数の数は？：',sympy.primepi(11))
print('2以上101未満の素数は？：',list(sympy.primerange(2, 101)))
print('101以上200未満の素数は？：',list(sympy.primerange(101, 200)))
print('11を超える2番目の素数：',sympy.nextprime(11,2))
print('12を超える2番目の素数：',sympy.nextprime(12,2))
print('199未満の素数で最も大きな数：',sympy.prevprime(199))
print('素数をランダムに発生させる：',sympy.randprime(100, 200))

5は素数か？： True
-5は素数か？： False
10番目の素数は？： 29
11以下の素数の数は？： 5
2以上101未満の素数は？： [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]
101以上200未満の素数は？： [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
11を超える2番目の素数： 17
12を超える2番目の素数： 17
199未満の素数で最も大きな数： 197
素数をランダムに発生させる： 191

sympy.isprime(ｎ)

引数で指定した値nが素数であればTrue、そうでなければFalseを返す

sympy.prime(ｎ)

小さいものから数えてn番目の素数を返す

sympy.primepi(ｎ)

n以下の素数の数を返す

sympy.primerange(n, m)

n以上m未満の素数を返す。リストになるのでlist関数と合わせて利用する。

sympy.nextprime(n,m)

nを超えてからm番目の素数を返す。

sympy.randprime(n,m)

指定した範囲の中で素数をランダムに返す。

素数の数を計算する

素数のリストを作成する

1～1000というような区分の中で、素数の数がいくつ分布しているかというのは非常に興味深いところです。そこで、10,000までの素数が1000単位の区分でいくつあるかを計算します。

SynPyで素数のリストを作成する

import sympy
prime_l=list(sympy.primerange(2,10000))
print(prime_l)
print(len(prime_l))

[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, （中略）
9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]
1229

SymPyモジュールのprimerange関数で簡単に計算することができます。リストprime_lに1229個の素数が収められているリストが作られます。

素数の数をカウントする

defaultdictを使った集計

素数の数を数えるプログラムです。前節で作ったリストの素数を1件ずつ読み込み、クラスごとに分類しています。

素数を区間ごとに集計する

import collections
d=len(str(max(prime_l)))
p_dict=collections.defaultdict(int)
interval=1000
for i in prime_l:
temp=int((i-1e-6)//interval)*interval
cls=f'{str(temp+1):>{d}}'+'-'+f'{str(temp+interval):>{d+2}}'
p_dict[cls]+=1
p_dict_s=dict(sorted(p_dict.items(), key=lambda x:x[0]))
p_dict_s

{'   1-  1000': 168,
 '1001-  2000': 135,
 '2001-  3000': 127,
 '3001-  4000': 120,
 '4001-  5000': 119,
 '5001-  6000': 114,
 '6001-  7000': 117,
 '7001-  8000': 107,
 '8001-  9000': 110,
 '9001- 10000': 112}

合計すると1229個と辻褄が合っています。

sympyモジュールで確認する

上記の結果を確認するために、sympyモジュールのprimerange関数を使って集計します。

SymPyモジュールのprimerange関数で確認する

import sympy
total=0
for i in range(10):
cnt=len(list(sympy.primerange(i*1000+1,(i+1)*1000+1)))
print(cnt)
total+=cnt
print(total)

正しく計算できたことがわかります。

Pythonで素数の計算をする

Pythonにより100までの素数を求める

素数の一覧を出力するプログラム

100未満の素数を列記する

3. jを約数の候補として、2から素数の候補であるiを順次割り算をしていきます。range(2.limit)については、後でもっと効率よくする方法を検討します。

4. ここであるjで割り切れる、つまり余りが0になったら、そのiは素数ではないので5.でbreakし次のiを素数であるか判定します。

6. iが素数であるときは、割ることができるjが存在しないので3.のforループから抜け、else節に入りその数を出力します。

7. print(i)とすると縦に表示されてしまうので、end=” ”とすることで横に並べて表示します。

素数の一覧をリストにする

100未満の素数をリストにする

2. 計算した素数をリストとして返すため、primeというリストを定義します。

8.9. 約数が見つからず素数として判断されるとprimeに使いされ、プログラムの最後で戻り値として返されます。

素数であるかを判定する

素数であるかを判定する関数

素数の定義に従ったプログラム

素数であるか判定する

2. 0や負数は素数ではないので、numが1以下であればFalseを出力します。

4. 1でない場合に5行目のelseに入ります。ここで6行目のfor文以下、約数の候補をiとして順次numを割り算します。余りが0になれば、Falseと表示してbreak文でforループから抜けプログラムは終了します。

9. for文でnumを割って余りが0になる数がない場合は素数となり、10行目のelse節に入り、Trueつまり素数と判断します。

フラグを使って少しだけすっきりとしたプログラム

フラグを使って素数であるか判定する

素数かどうかを判断するプログラムを関数にする

素数かどうかを判定する関数

素数かどうかを判断する関数を活用する

ある数値の範囲にある素数をリストで返す関数

ある範囲にある素数をリストにする関数

3. for文のrangeで、変数iを素数の候補として、lowerからupper-1までループするので結果的にlower以上upper未満の間で素数か否かを判断することができます。

4. is_prime関数を使い、iが素数かどうかを判断します。if is_prime(i)はif is_prime(i)==True:と同じ意味です。ここで素数であればリストprimeに追加します。

6. forループを抜けると7行目でprimeを返してプログラムが終了です。

素数を小さい順番に並べてn番目の素数を求める関数

小さい順に並べてcnt番目の素数を求める関数

2. iを素数の候補として3行目で定義します。

3. cnt番目の関数を求めることから、iをいくつまで調べればよいかわかりません。このような場合、4行目ではfor文に代えてwhile文を使い、素数が10個見つかるまでループを回すようにします。

ある数を超えて小さい順にn番目の素数を求める関数

ある数を超えて小さい順にcnt番目の素数を求める関数

3. 素数の候補として引数から渡ってきたbaseを使います。4行目でbaseに1を足しているので、引数のbase+1から素数の判定を行います。

8.9. 結果を比較すると、baseで渡した値を超えた数で計算できていることがわかります。

ある数未満で大きい順にcnt番目の素数を求める関数

ある数未満で大きい順にcnt番目の素数を求める関数

Sympyの素数に関する関数

Sympyの素数に関する関数

素数の数を計算する

素数のリストを作成する

SynPyで素数のリストを作成する

素数の数をカウントする

defaultdictを使った集計

素数を区間ごとに集計する

sympyモジュールで確認する

SymPyモジュールのprimerange関数で確認する

3.　jを約数の候補として、2から素数の候補であるiを順次割り算をしていきます。range(2.limit)については、後でもっと効率よくする方法を検討します。

4.　ここであるjで割り切れる、つまり余りが0になったら、そのiは素数ではないので5.でbreakし次のiを素数であるか判定します。

6.　iが素数であるときは、割ることができるjが存在しないので3.のforループから抜け、else節に入りその数を出力します。

7.　print(i)とすると縦に表示されてしまうので、end=” ”とすることで横に並べて表示します。

2.　計算した素数をリストとして返すため、primeというリストを定義します。

2.　0や負数は素数ではないので、numが1以下であればFalseを出力します。

4.　1でない場合に5行目のelseに入ります。ここで6行目のfor文以下、約数の候補をiとして順次numを割り算します。余りが0になれば、Falseと表示してbreak文でforループから抜けプログラムは終了します。

9.　for文でnumを割って余りが0になる数がない場合は素数となり、10行目のelse節に入り、Trueつまり素数と判断します。

3.　for文のrangeで、変数iを素数の候補として、lowerからupper-1までループするので結果的にlower以上upper未満の間で素数か否かを判断することができます。

4.　is_prime関数を使い、iが素数かどうかを判断します。if is_prime(i)はif is_prime(i)==True:と同じ意味です。ここで素数であればリストprimeに追加します。

6.　forループを抜けると7行目でprimeを返してプログラムが終了です。

2.　iを素数の候補として3行目で定義します。

3.　cnt番目の関数を求めることから、iをいくつまで調べればよいかわかりません。このような場合、4行目ではfor文に代えてwhile文を使い、素数が10個見つかるまでループを回すようにします。

3.　素数の候補として引数から渡ってきたbaseを使います。4行目でbaseに1を足しているので、引数のbase+1から素数の判定を行います。