素数判定プログラムを作る（Python）

最近、今更ながら数学を勉強しています。
以前サラッと勉強した機械学習をちゃんとやろうと思うと、微分が避けて通れず・・・

時々Python もコード書かないと、どんどん忘れちゃうので今日は素数を判定するプログラムを簡単に書きました。

1. 2〜100までの整数から素数を見つけるプログラム

コードは以下の通りです。

#2〜１００までの値を順番に変数numに格納してループを実行
for num in range(2, 101):
  #2は素数なので問答無用で出力
  if num == 2:
    print(num)
  #2以降について判定を実施
  else:
    #２〜変数numに格納された数字まで順番に変数nに格納していく
    for n in range(2, num):
      #変数numを変数nで割り切れたら処理終了
      if num % n == 0:
        break
      #変数nが変数numから１引いた数まで処理継続していたら、素数なので変数numを出力
      elif n == num - 1:
        print(num)
      else:
        #途中経過で割り切れてはいないので処理継続
        pass

(1) 素数とは

素数とは、自身でしか割り切ることができない数。
約数が1か自身となる数です。

つまり、判定対象とする数字まで2から順番に割っていって余が0にならないまま、判定対象とする数字から1引いた数となった場合、その数は素数と判定できます。

(2) コード解説

なので、このプログラムのメイン部分は以下です。

    for n in range(2, num):
      #変数numを変数nで割り切れたら処理終了
      if num % n == 0:　#①
        break #②
      #変数nが変数numから１引いた数まで処理継続していたら、素数なので変数numを出力
      elif n == num - 1: #④
        print(num) #⑤
      else:
        #途中経過で割り切れてはいないので処理継続
        pass　＃③

変数numは判定対象の数字です。

2から順番に判定対象の数字から1引いた数までを変数nに格納しては、numをnで割り切れるかをチェック(①)、割り切れたらループ処理をbreakで抜けて即終了(②)、次の変数numに移ります。

nがnumから1引いた数にもなっておらず、numをnで割り切れなかった場合はpassで次の変数nに移ります。(③)

もし変数nがループ処理をしていった結果、変数numから1引いた数まで達したら(④)、それは1か自身でしか割り切れないことになるので、素数として出力します。(⑤)

(3)コード実行

では実行してみます。

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.応用　自分で指定した範囲の中で素数を見つけるプログラム

少し応用して、自分で指定した範囲の中から、素数を見つけるプログラムにバージョンアップさせます。

#開始フラグを定義
start_flug = 0

#開始フラグが０だと繰り返し
while start_flug == 0:
  #未入力や数字以外の場合はエラーで落とす
  try:
    start_num = int(input('チェックを開始する数字（２以上）'))
    end_num = int(input('チェックを終了する数字（チェックを開始する数字以上）'))
    #チェック開始する数字が１以上か、チェック終了する数字はチェック開始の数字とイコールまたはそれ以上か
    if start_num > 1 and end_num >= start_num:
      start_flug = 1
    else:
      #チェックに引っかかったらstart_flugは１とせず再入力させる
      print('チェックを開始する数字は2以上の数字を入力してください、チェックを終了する数字は開始する数字以上を入力してください')
  except Exception as e:
    print('数字を入力してください')

#素数を格納するリストを作成
prime_number_list = []

#素数かどうかを判定する処理
for num in range(start_num, end_num+1):
  if num == 2:
    prime_number_list.append(num)
  else:
    #判定対象とする数字を2から判定対象とするまでの数−１まで順番に余が出ないか（割り切れるか）チェック
    for n in range(2, num):
      if num % n == 0:
        break
      elif n == num -1:
        prime_number_list.append(num)
      else:
        pass

#ループ処理が終了したら、チェック完了メッセージとチェック開始・終了した数字、見つけた素数の個数を出力
print('\nチェック完了\n')
print("・{}から{}までの間で素数をチェック\n・素数の個数：{}\n".format(start_num, end_num, len(prime_number_list)))

#forループで素数を一つずつ出力する
print('以下が素数です')
print('----------------------------------------------------------------------')
for index, prime_num in enumerate(prime_number_list):
  if (index + 1) % 10 == 0:
    print(prime_num, ',\n')
  else:
    print(prime_num, end=', ')
print('\n----------------------------------------------------------------------')

(1)入力チェック

#開始フラグを定義
start_flug = 0 #①

#開始フラグが０だと繰り返し
while start_flug == 0:　#②
  #未入力や数字以外の場合はエラーで落とす
  try: #⑨
    start_num = int(input('チェックを開始する数字（２以上）'))　＃③
    end_num = int(input('チェックを終了する数字（チェックを開始する数字以上）')) #④
    #チェック開始する数字が１以上か、チェック終了する数字はチェック開始の数字とイコールまたはそれ以上か
    if start_num > 1 and end_num >= start_num: ＃⑤
      start_flug = 1 #⑥
    else: #⑦
      #チェックに引っかかったらstart_flugは１とせず再入力させる
      print('チェックを開始する数字は2以上の数字を入力してください、チェックを終了する数字は開始する数字以上を入力してください')　＃⑧
  except Exception as e: #⑩
    print('数字を入力してください')

チェック開始する数字と、チェック終了する数字が正しく入力されていないと、処理がエラーとなり終了してしまいます。

なので、入口の時点で入力チェックをし、正しくなければ正しく入力がされるまで処理を開始させないようにしています。

開始フラグとして、変数start_flugを定義(①)しwhileループでstart_flugが0である限りで入力をさせます。(②)

標準入力（ユーザーにターミナル上で入力させる）はinput()で実装できます。なお、入力されたものは文字列として扱われるため、今回のように数値として扱いたい場合は、int(input())とする必要があります。(③・④)

素数かをチェックする際、2以上の数字がチェック開始の数字として入力されているか、チェック終了の数字は開始の数字以上かを確認し(⑤)、問題なければstart_flugを1に更新し(⑥)、おかしければ再入力をさせています。(⑦・⑧）

なお、そもそも未入力や文字が入力されるケースもあるでしょう。
その場合は、処理自体がこけてしまうので、try・exceptを使い、まずはtry節で入力チェック処理をし(⑨）、そもそも未入力や文字の場合はexcept節の例外処理の方に流すことでエラーでこけないようにしています。(⑩）

(2) 素数判定処理

違い目としては先ほど2〜100までと範囲を決め打ちしていた部分が可変となったので、それぞれstart_num変数と、end_num変数を利用してチェック範囲を可変としています。　(①)

#素数を格納するリストを作成 #②
prime_number_list = []

#素数かどうかを判定する処理
for num in range(start_num, end_num+1):　#①
  if num == 2:
    prime_number_list.append(num) #③
  else:
    #判定対象とする数字を2から判定対象とするまでの数−１まで順番に余が出ないか（割り切れるか）チェック
    for n in range(2, num):
      if num % n == 0:
        break
      elif n == num -1:
        prime_number_list.append(num)
      else:
        pass

後は、後で素数の数等を出力するにあたり、リストに判定された素数を格納すると後で扱いやすくなるため、prime_number_listを用意(②)

素数判定された数をリストに追加していく処理をしています。(③）

(3) 結果出力

最後にせっかくここまで書いたので、出力も少し工夫します。

どの範囲をチェックしたのか、素数はいくつ見つかったのか、具体的に素数と判定された数はなんだったのかを出力します。

#ループ処理が終了したら、チェック完了メッセージとチェック開始・終了した数字、見つけた素数の個数を出力
print('\nチェック完了\n')
print("・{}から{}までの間で素数をチェック\n・素数の個数：{}\n".format(start_num, end_num, len(prime_number_list)))　#①

#forループで素数を一つずつ出力する
print('以下が素数です') #②
print('----------------------------------------------------------------------')
for index, prime_num in enumerate(prime_number_list):　　#③
  if (index + 1) % 10 == 0: #④
    print(prime_num, ',\n')　#⑤
  else:
    print(prime_num, end=', ')#⑥
print('\n----------------------------------------------------------------------')

数が多かった場合、縦にひたすら表示されるとみづらいので、10個までは
改行されずに出力(⑥)し、10個目は改行する（④・⑤）ようにしています。

enumerate()を利用することで、インデックスも扱えるようになります。(③)

(4) コード実行

では、試しに55555〜56800までの間の整数の素数判定をしてみます。

チェックを開始する数字（２以上）55555
チェックを終了する数字（チェックを開始する数字以上）56800

チェック完了

・55555から56800までの間で素数をチェック
・素数の個数：121

以下が素数です
----------------------------------------------------------------------
55579, 55589, 55603, 55609, 55619, 55621, 55631, 55633, 55639, 55661 ,

55663, 55667, 55673, 55681, 55691, 55697, 55711, 55717, 55721, 55733 ,

55763, 55787, 55793, 55799, 55807, 55813, 55817, 55819, 55823, 55829 ,

55837, 55843, 55849, 55871, 55889, 55897, 55901, 55903, 55921, 55927 ,

55931, 55933, 55949, 55967, 55987, 55997, 56003, 56009, 56039, 56041 ,

56053, 56081, 56087, 56093, 56099, 56101, 56113, 56123, 56131, 56149 ,

56167, 56171, 56179, 56197, 56207, 56209, 56237, 56239, 56249, 56263 ,

56267, 56269, 56299, 56311, 56333, 56359, 56369, 56377, 56383, 56393 ,

56401, 56417, 56431, 56437, 56443, 56453, 56467, 56473, 56477, 56479 ,

56489, 56501, 56503, 56509, 56519, 56527, 56531, 56533, 56543, 56569 ,

56591, 56597, 56599, 56611, 56629, 56633, 56659, 56663, 56671, 56681 ,

56687, 56701, 56711, 56713, 56731, 56737, 56747, 56767, 56773, 56779 ,

56783, 
----------------------------------------------------------------------

なんと、Numberpediaというサイトがあり整数の性質や関連する数列について記載を確認できます。
試しに56197は本当に素数か見てみましょう。

確かに素数でした。

3.最後に

こんな感じで、他愛のない要件でもどうやって実装すべきかを考えるのはとても頭の体操になりますし、楽しいです。

読んでいただきありがとうございました！