Pythonで素数の計算をする

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

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

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

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

  1. #1 100未満の素数を列記する
  2. limit = 100
  3. for i in range(2, limit):
  4. for j in range(2, i):
  5. if i % j == 0:
  6. break
  7. else:
  8. 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

  1. 3行目でiを素数の候補とし、2からlimit(=100)までfor文でループして素数であるかを調べます、2からとしているのは1は素数でないためです。また、range関数は2番目の引数より1つまえで処理を終えてしまうので、limitとするとその数未満ということになります。未満ではなく以下としたい場合はlimit+1とします。
  2. 4行目ではjを割ることができる数の候補として、2から素数の候補であるiを次々と割り算をしていきます。
  3. ここであるjで割り切れる、つまり余りが0になったら、そのiは素数ではないので7行目でbreakし次のiを素数であるか判定します。
  4. あるiが素数であるときは、割ることができるjが存在しないので5行目のforループから抜けるので、7行目のelse節に入りその数を出力します。print(i)とすると縦に表示されるので、end=” ”とすると横に並べて表示されます。
  5. 3行目のrange(2.i)については、後でもっと効率的な方法にするよう検討します。

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

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

  1. #2 100未満の素数をリストにする
  2. limit = 100
  3. prime = []
  4. for i in range(2, limit):
  5. for j in range(2, i):
  6. if i % j == 0:
  7. break
  8. else:
  9. prime.append(i)
  10. print(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]

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

素数であるかを判定する

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

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

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

  1. #3 素数であるか判定する
  2. num = 36
  3. if num <= 1:
  4. print(False)
  5. else:
  6. for i in range(2, int(num**0.5)+1):
  7. if num % i == 0:
  8. print(False)
  9. break
  10. else:
  11. print(True)

False

  1. 2行目で1、0や負数は素数ではないのでnumが1以下であればFalseを出力します。
  2. for文の2番目の引数をnumではなくint(num**0.5)+1と変更します。なぜなら、例えば36の約数を考えると、積が36になるような組み合わせは (1,36)、(2,18) 、(3,12) 、(4,9)、(6,6)となります。このことから、素数ではない場合、2からnumの平方根までの間に必ず約数が存在するので、その間に約数がなければ素数と判断できるためです。またint関数を使うのは、平方根が整数にならないとfor文がエラーになるので、切り捨てて整数にそろえるためです。
  3. 1でない場合に5行目のelseに入ります。ここで6行目のfor文以下、約数の候補をiとして順次numを割り算します。余りが0になれば、Falseと表示してbreak文でforループから抜けプログラムは終了します。
  4. 6行目のfor文でnumを割って余りが0になる数がない場合は素数となり、10行目のelse節に入り、Trueつまり素数と判断します。

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

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

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

  1. #4 フラグを使って素数であるか判定する
  2. num = 36
  3. flg = False
  4. for i in range(2, int(num**0.5)+1):
  5. if num % i == 0:
  6. break
  7. else:
  8. flg = True
  9. print(flg)

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

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

  1. # 5 素数かどうかを判定する関数
  2. def is_prime(i):
  3. if i <= 1:
  4. return False
  5. for j in range(2, int(i**0.5) + 1):
  6. if i % j == 0:
  7. return False
  8. return True
  10. print('1は素数？',is_prime(1))
  11. print('2は素数？',is_prime(2))
  12. print('8は素数？',is_prime(8)) 

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

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

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

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

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

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

  1. #6 ある範囲にある素数をリストにする関数
  2. def prime_range(lower,upper):
  3. prime = []
  4. for i in range(lower, upper):
  5. if is_prime(i):
  6. prime.append(i)
  7. return prime
  9. print('1以上100未満の素数のリスト：',prime_range(1,100))
  10. print('100以上200未満の素数のリスト：',prime_range(100,200))
  11. 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]

  1. 4行目のfor文のrangeで、変数iを素数の候補として、lowerからupper-1までループするので結果的にlower以上upper未満の間で素数か否かを判断することができます。
  2. 5行目でis_prime関数を使い、iが素数かどうかを判断します。if is_prime(i)はif is_prime(i)==True:と同じ意味です。ここで素数であればリストprimeに追加します。
  3. forループを抜けると7行目でprimeを返してプログラムが終了です。

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

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

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

  1. #7 小さい順に並べてcnt番目の素数を求める関数
  2. def prime_seq(cnt):
  3. i = 1
  4. while 0 < cnt:
  5. i += 1
  6. if is_prime(i):
  7. cnt -= 1
  8. return i
  10. print('1番目の素数：',prime_seq(1))
  11. print('5番目の素数：',prime_seq(5))

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

  1. iを素数の候補として3行目で定義します。
  2. cnt番目の関数を求めることから、iをいくつまで調べればよいかわかりません。このような場合、4行目ではfor文に代えてwhile文を使い、素数が10個見つかるまでループを回すようにします。
  3. 5行目でiに1をどんどん足しこんでいくので、2から順番に素数であるか否かを判断することになります。is_prime関数で素数と判断したときにはcntを1つ減らします。この結果、cntとして渡した数だけ素数が見つかるとcnt=0となり4行目のwhileループが終了します。このときのiはcnt番目の素数となります。

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

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

  1. #8 ある数を超えて小さい順にcnt番目の素数を求める関数
  2. def prime_next(base,cnt=1):
  3. while(cnt>0):
  4. base+=1
  5. if is_prime(base):
  6. cnt -=1
  7. return base
  9. print('100を超えて2番目の素数：',prime_next(100,2))
  10. print('101を超えて2番目の素数：',prime_next(101,2))
  11. print('100を超えて次の素数：',prime_next(100))

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

  1. 素数の候補として引数から渡ってきたbaseを使います。4行目でbaseに1を足しているので、引数のbase+1から素数の判定を行います。
  2. 9行目、10行目の結果を比較すると、baseで渡した値を超えた数で計算できていることがわかります。
  3. 2行目でcnt=1として関数に渡しているのは、11行目の実行例のように、2番目のcntを省略すると関数は既定値（default）で1をセットしてプログラムを実行できるようにするためです。

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

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

  1. #9 ある数未満で大きい順にcnt番目の素数を求める関数
  2. def prime_pre(base, cnt=1):
  3. while(cnt > 0):
  4. base -= 1
  5. if is_prime(base):
  6. cnt -=1
  7. return base
  9. print('100未満で大きい方から2番目の素数：',prime_pre(100, 2))
  10. print('101未満で大きい方から2番目の素数：',prime_pre(100, 2))
  11. print('100未満で最大の素数：',prime_pre(100))

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

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

Sympyの素数に関する関数

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

  1. #10 Sympyの素数に関する関数
  2. #10 Sympyの素数に関する関数
  3. import sympy
  4. print('5は素数か？：',sympy.isprime(5))
  5. print('-5は素数か？：',sympy.isprime(-5))
  6. print('10番目の素数は？：',sympy.prime(10))
  7. print('101以下の素数の数は？：',sympy.primepi(101))
  8. print('101以上200未満の素数は？：',list(sympy.primerange(2, 101)))
  9. print('101以上200未満の素数は？：',list(sympy.primerange(101, 200)))
  10. print('100を超える素数で2番目に小さい数：',sympy.nextprime(100,2))
  11. print('101を超える素数で2番目に小さい数：',sympy.nextprime(101,2))
  12. print('200を未満の素数で最も大きな数：',sympy.prevprime(200))
  13. print('素数をランダムに発生させる：',sympy.randprime(100, 200))

5は素数か？： True
-5は素数か？： False
10番目の素数は？： 29
101以下の素数の数は？： 26
101以上200未満の素数は？： [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]
100を超える素数で2番目に小さい数： 103
101を超える素数で2番目に小さい数： 107
200を未満の素数で最も大きな数： 199
素数をランダムに発生させる： 127

sympyモジュールで素数であるかを判定する関数
sympy.isprime(ｎ)

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

sympyモジュールで関数
sympy.prime(ｎ)

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

sympyモジュールで関数
sympy.primepi(7) (ｎ)

引数で指定した数値より小さい素数の数を返す

sympyモジュールで関数
sympy.primerange(101, 200)

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

sympyモジュールで関数
sympy.nextprime(10,1)

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

ympy.randprime(100, 200)

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