みんな、素数見ると絶頂するよね？
皆様ごきげんようです。いぬころんです。
生まれは1990年。 すぐ素数ではないと判別できる偶数年生まれです。
なお、和暦では平成2年。 最小の素数年生まれです。
(弟は西暦素数年、和暦非素数年生まれです。)
そんなわけで今回は素数に関するプログラムを2つ作ってみました。
東京工業大学の皆様にはきっと受けるはず！
※素数羅列プログラムのファイルとコードを更新しました。
変わった点は最後の「更新」見出しをご参照ください。
ファイルダウンロード
素数羅列プログラム
素数判定プログラム
サンプル画像
コード
①素数羅列
# 以下本体＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
# 元気に挨拶
from typing import List
print("一花の素数表示プログラムへようこそ！\n"
"このプログラムでは指定した数以下の自然数から\n"
"素数を判別、一覧で表示します。")
while True:
# 最後の「もう一度やる」で「n」を入力するまでループ
while True:
# 数字が正常に入力されるまでループ
try:
num = int(input("数字を入力＞＞＞"))
except ValueError:
print("整数以外が入力されました。")
continue
if num <= 0:
print("定義上、素数は自然数のみです。正の整数を入力してください。")
continue
break
print("準備中です。")
# 判定対象の数字をリスト化。指定した数が大きいほど時間はかかる。
judges: list[int] = [candidate for candidate in range(1, num + 1)]
# input("Enterで開始。")
print("判定中です。")
# 以下素数判定。
# 素数と判定された数字の倍数は素数ではないため判定対象から除外。
# 素数と判定された数字は素数リストに格納。
primenumbers = []
index = 0
while index < len(judges):
if not judges[index]:
# 判定済みの素数の倍数だった数字は判定スキップ。
index += 1
continue
if judges[index] == 1:
# print("%10dは素数ではありません。約数が１つだけです。"%(judges[0]))
index += 1
continue
primenumbers.append(judges[index])
# print(("%10dは素数です。")%judges[index])
# 判定対象の数字が素数だった場合、その数字の倍数を判定対象から除外
subindex = index + judges[index]
if subindex < len(judges):
while subindex < len(judges):
if judges[subindex]:
# print("%10d:%10dで割り切れます。素数ではありません。" % (judges[subindex], judges[index]))
judges[subindex] = False
subindex += judges[index]
index += 1
# 素数リストに格納されていた素数の数を表示
print(primenumbers)
print("素数は全部で%10d個ありました。" % (len(primenumbers)))
# 任意の素数をピックアップ
print("上記の素数から一つ取り出してみましょう。")
while True:
try:
index = int(input("何番目の素数を取り出すか、%d～%dまでの間で\n"
"数字を入力してください。\n"
"＞＞＞" % (1, len(primenumbers))))
except ValueError:
print("自然数を入れてください。")
continue
if index < 1 or index > len(primenumbers):
print("数字は%d～%dの間で入力してください。" % (1, len(primenumbers)))
continue
print("%d個目の素数は%dです。" % (index, primenumbers[index - 1]))
while True:
more = input("別の素数も取り出してみますか？\n"
"y：はい\n"
"n：いいえ\n"
"＞＞＞")
if more != "y" and more != "n":
print("答えは「y」か「n」で入力してください。")
continue
break
if more == "y":
continue
else:
break
# 再利用希望確認。「n」入力で終了フェーズへ
while True:
replay = input("もう一度はじめからやってみますか？\n"
"y：はい\n"
"n：いいえ\n"
">>>")
if replay != "y" and replay != "n":
print("答えは「y」か「n」で入力してください。")
continue
break
if replay == "y":
continue
else:
break
input("Enterで終了します。")
②素数判定
while True:
while True:
try:
num = int(input("数字を入れてください。(2以上)>>>"))
except ValueError:
print("整数以外が入力されました。やり直しです。")
continue
if num < 2:
print("2以上の数字を入れてください。")
continue
while True:
start = input("%dで検証しますか？\n"
"y：はい\n"
"n：設定し直す\n"
"＞＞＞" % (num))
if start != "y" and start != "n":
print("答えは「y」か「n」で入力してください。")
continue
else:
break
if start == "y":
break
if start == "n":
continue
while True:
print("%dが素数か否か検証中です。" % (num))
div = 2
while div < num//2:
if num % div == 0:
print("%dは%dで割り切れます。素数では有りません。" % (num, div))
break
div += 1
if div == num//2:
print("%dは素数でした。" % (num))
break
break
while True:
restart = input("もう一度やりますか？\n"
"y：はい\n"
"n：終わります\n"
"＞＞＞")
if restart != "y" and restart != "n":
print("答えは「y」か「n」で入力してください。")
continue
break
if restart == "y":
continue
else:
break
input("Enterで終了")
参考
自然数nが素数かどうかを判別するためには、１とn以外にnの約数があるか
調べていく必要があります。
よって２からn-1までのすべて数字でnを割って、
どこかの数字で剰余が0となった場合、その数字は非素数、
すべての数字で剰余1以上なら素数となります。
また、自然数nが素数じゃない場合、
1の次に小さな約数は最低でも2以上となるため、
2番目に大きい約数は「n/2以下」ということになります。
よって素数かどうかを判定する場合、
「２以上n/2以下の全自然数で割った結果」を調べれば良いことになり、
繰り返し構文を実行する上でできるだけ処理を短時間に出来るよう工夫しています。
なお、素数羅列プログラムでは、
これまでに素数だとわかってい数の倍数を素数候補から外し、
その生き残りの数字のうち最小のものを次の判定対象にしています。
よって、剰余0のパターン有無の判定にかけられる数字は
それまでに判明している素数の倍数ではないため、判定開始は
「”n/(既知最大素数)”を”既知最大素数”で割る」ところから始めています。
これにより、大きい数字まで判定したい場合でも処理速度の遅延を
防ぐことができます！
更新
素数羅列プログラムを更新いたしました。
初稿時点では直前の説明にあるように既知最大素数を活用し、
剰余有無確認作業を最小回数で留める工夫をしていますが、
根本的に割り算の計算を行わずとも判定できることがわかったためです。
はじめに１から指定した数までをリスト化し、
１は例外処理で素数でない旨判定、素数候補リストから外し、
２を素数と判定、２の倍数を素数候補から外します。
候補から外すということで「.remove」を活用したいところですが、
最初に指定した数字が大きくリスト自体が長くなってきた場合、
そのリスト全体を逐一参照することになるため処理速度が落ちます。
そのため、2の倍数をリストから消すのではなく、2の倍数部分を
「False」のブール値に変換します。
この時点で１と2以外の2の倍数は「False」に変換され、
残った候補内の最小「３」を次の素数と判定、３の倍数を「False」に変換。
残った候補の最小値は２の倍数でFalseにされた４の次「５」となり、
同じ作業を繰り返していくと「７・１１・１３・・・」と
残りリスト内の最小数値が次の素数であるとわかります。
なお、リスト内のインデックス番号を”index=0”→”index+=1”で調整し、
参照先がすでに過去の素数の倍数としてFalseとなっている場合は
何もせずに次のインデックスに参照先が進みます。
「min」などを使った場合、やはりリスト全体参照が必要となりますし、
そもそも「True・False」が「０・１」と扱われることから、
３以上の数値の判定時点でコケます。
そんなわけで、剰余を計算する必要がなくなった結果、
掛け算割り算などの処理が不要となり、
実質足し算のみで判定できるようになりました。
これは以前C言語の話で聞いたことがあるのですが、
足し算引き算と掛け算割り算で処理時間を比べた場合、
足し算引き算のほうが処理時間は短くなると聞きました。
(言語によるのかもしれませんが、アルゴリズム的に基本変わらないかと。)
微々たるものではあると思いますが、繰り返し計算をすることを考えれば、
できるだけ短い処理時間で終われるようにするため
足し算引き算で対応できるのが最適ということになるでしょう。
ただし、無理やり足し算引き算になることで周りのコードが肉厚になるなら
話は別だと考えてください。
今回は個人で作成しているネタプログラムですが、
共同開発を行う場合など、チーム全員にわかりやすいコードのほうが
運営しやすいこともあるはずです。
以上、更新も終わりましたので素数記事はこれにて終了いたします。
素数で絶頂できなかった残念なあなたはスキボタンを押して
次に備えておきましょう！(催促)
いいなと思ったら応援しよう！
