先日に引き続き、素数のプログラムです。
先日のは素数を見つけて列挙するものでしたが、今回のプログラムは
これまでに見つけた素数をもとに素数を生成するアプリとなっています。
ファイルダウンロード
ソースコード
def inputnum():
while True:
num = input("数字を入力してください▶")
if num:
try:
int(num)
except ValueError:
interror()
continue
else:
nullerror()
continue
num = int(num)
if num <= 1:
numerror()
continue
break
return num
def numerror():
print("文字が入力されています。")
def interror():
print("自然数を入力してください。")
def numerror():
print("2よりも大きい数字を入力してください。")
def nullerror():
print("何も入力されていません。")
print("いぬころんの超大素数生成アプリへようこそ!\n"
"このプログラムでは入力した数字以下の素数を判定し、\n"
"見つかった素数をすべてかけ合わせた数+1の数字を計算し、\n"
"見つからなかった大きい数字の素数を探索するプロジェクトです。")
num = inputnum()
print("まずは%d以下の素数を判定します。" % (num))
JudgeList = [True] * num
input("Enterを押してスタートします。")
judging = 0
PrimeNumbers = []
while True:
if judging == 0:
JudgeList[judging] = False
judging += 1
continue
if not JudgeList[judging]:
judging += 1
continue
else:
print("%10d:素数です。" % (judging + 1))
PrimeNumbers.append(judging + 1)
if (judging + 1) ** 2 > num:
judging += 1
break
deleting = (judging + 1) ** 2 - 1
while True:
print("%10d:%10dで割り切れるため素数ではありません。" % (deleting + 1, judging + 1))
JudgeList[deleting] = False
deleting += judging + 1
if deleting + 1 > len(JudgeList):
break
judging += 1
while True:
if not JudgeList[judging]:
judging += 1
else:
print("%10d:素数です。" % (judging + 1))
PrimeNumbers.append(judging + 1)
judging += 1
if judging == len(JudgeList):
break
print("指定した範囲で見つかった素数の数:%d個" % (len(PrimeNumbers)))
input("Enterを押して大きい素数を計算します。")
maxprime = 1
index = 0
while True:
maxprime *= PrimeNumbers[index]
index += 1
if index == len(PrimeNumbers):
maxprime += 1
break
print("今回の調査で確認できた最大の素数は以下の数字です。\n"
"%d" % maxprime)
input("Enterを押すと終了します。")
素数の精製方法
素数は無限にあるということが知られています。
証明方法として、有る素数Pがあるとき、
2からPをすべてかけ合わせた数字に1を足した場合、
素数である2からPのどの数字で割も1余るため、
その数字は素数だということがわかるからです。
(※例えば、素数である2,3,5,7をすべてかけ合わせて1を足すと211が素数。)
この証明方法を活用すると、ある程度の個数の素数を探しておけば、
その素数すべてをかけ合わせて1を足すことで、
簡単に大きな素数を探すことが出来ます。
ちなみに、10000以下の素数を探して上記の計算を行ってできた最大素数は
下記のとおりです。
4298桁ありました\(^o^)/どっひゃー