素数判定プログラムリターンズ
皆さまお久しぶりです。
いぬころんです。
以前、素数判定プログラムのプログラムを公開し、はや一年以上。
この度、色々と収穫を得てプログラムの軽量化を致しました。
ついでに、指定した数の中だけの素数を表示してくれる機能も今回新たに追加しましたのでぜひお試しくださいませ。
ファイルダウンロード
ソースコード
def inputnum(x):
while True:
if x == 1:
num = input("最小値を入力してください▶")
else:
num = input("最大値を入力してください▶")
if num:
try:
int(num)
except ValueError:
interror()
continue
else:
nullerror()
continue
num = int(num)
if num <= 0:
minuserror()
continue
break
return num
def searching(x):
while True:
index = input("何番目の素数を抜き出しますか?(%d以下の数字を入力。)" % x)
if index:
try:
int(index)
except ValueError:
interror()
continue
else:
nullerror()
continue
index = int(index)
if index > x:
print("範囲外の数字が入力されました。")
continue
break
return index
def rangeerror():
print("最大値は最小値よりも大きい数字を入力してください。")
def numerror():
print("文字が入力されています。")
def interror():
print("自然数を入力してください。")
def minuserror():
print("0よりも大きい数字を入力してください。")
def nullerror():
print("何も入力されていません。")
##########以上関数##########
##########以下本体##########
# ウェルカムメッセージ
print("いぬころんの素数判定アプリへようこそ!\n"
"このプログラムでは入力した2つの数字以内の素数を一覧で表示します。")
phase = 1
# 最小値入力
minimum = inputnum(phase)
phase += 1
# 最大値入力・最小値より大きな数字が入力されるまで繰り返す。
while True:
maximum = inputnum(phase)
if maximum <= minimum:
rangeerror()
continue
break
print("準備しています。")
# 最大値と同数の「True」をリスト化
JudgeList = [True] * maximum
print("判定中です。")
# 判定フェーズ1スタート・素数判定した数字の2乗が最大値より大きい場合に終了
judging = 0
PrimeNumbers = []
while True:
if judging == 0:
# 1は素数ではないため例外処理
JudgeList[judging] = False
judging += 1
continue
if not JudgeList[judging]:
# 2以降の数字について、判定する数字がすでに素数ではないと判定された場合はスキップ
judging += 1
continue
else:
# 要素が「True」の場合は素数として認定し、インデックスの数字をもとに素数リストに追加。
if judging + 1 >= minimum:
PrimeNumbers.append(judging + 1)
if (judging + 1) ** 2 > maximum:
judging += 1
break
deleting = (judging + 1) ** 2 - 1
while True:
# 素数判定した数字の倍数を素数ではないものとして「False」に変更
if deleting + 1 >= minimum:
# print("%10d:%10dで割り切れるため素数ではありません。" % (deleting + 1, judging + 1))
JudgeList[deleting] = False
deleting += judging + 1
if deleting + 1 > len(JudgeList):
break
judging += 1
# 判定フェーズ2スタート・判定フェーズ1で非素数と判定されなかったものは素数となる
while True:
if not JudgeList[judging]:
judging += 1
else:
if judging >= minimum:
PrimeNumbers.append(judging + 1)
judging += 1
if judging == len(JudgeList):
break
if len(PrimeNumbers) >= 1:
input("判定が終わりました。Enterを押して一覧を表示します。")
index = 0
while True:
print("%12d" % PrimeNumbers[index])
index += 1
if index == len(PrimeNumbers):
break
print("指定した範囲で見つかった素数の数:%d個" % (len(PrimeNumbers)))
print("素数を抜き出してみましょう。")
showindex = searching(len(PrimeNumbers))
print("%d個目の素数は%dです。" % (showindex, PrimeNumbers[showindex - 1]))
else:
print("指定した数に間に素数はありませんでした")
input("Enterを押すと終了します。")
どんなアルゴリズム?
今回のプログラムでは、素数を判定する有名なアルゴリズム
「エラトステネスの篩」を忠実に再現しています。
参考:エラトステネスの篩の唄
仮に100までの素数を求めよと言われた場合のアルゴリズムを
順を追って箇条書いたします。
今回のプログラムではこのリストを作る際に、全て「True」を要素に、
100までの素数を探す場合は「True」が100個のリストを作成しています。
数字の連番でリストを作るよりもリストの生成が早いためです。
素数番目のTrueはそのままにして、素数の倍数番目のTrueをFalseに変更し
素数か素数ではないかを判定するスタイルを取っています。
なお、③の作業ではじめに篩い落とす数字がその素数の2乗なのは、
その素数の2乗以下の倍数は、これまでの素数の倍数を篩い落とすときに
すでに篩い落とされているのが確定しているからです。
例えば、11の倍数を篩い落とす場合、はじめに篩い落とすのは
11の2乗▶121ですが、これまでの「22,33,44,,,110」はどれも11の倍数であると同時に「2の倍数,3の倍数,4の倍数,,,10の倍数」でもあります。
よって、これまでに素数か否か判定した数字の倍数なので、
すでに篩い落とされたあとだということがわかります。
これも単純に素数の倍数をふるい落としてもいいのですが、
無駄な作業が減るので効率化出来ます。
以上でございます。
記事をご覧頂きまして、まことにありがとうございます。 「缶コーヒーの差し入れ」くらいの気持ちでサポートをしてくれされば とても励みになります。