皆さまお久しぶりです。
いぬころんです。

以前、素数判定プログラムのプログラムを公開し、はや一年以上。
この度、色々と収穫を得てプログラムの軽量化を致しました。
ついでに、指定した数の中だけの素数を表示してくれる機能も今回新たに追加しましたのでぜひお試しくださいませ。

ファイルダウンロード

ソースコード

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("判定中です。")

# 判定フェーズ１スタート・素数判定した数字の２乗が最大値より大きい場合に終了
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

# 判定フェーズ２スタート・判定フェーズ１で非素数と判定されなかったものは素数となる
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の倍数」でもあります。
よって、これまでに素数か否か判定した数字の倍数なので、
すでに篩い落とされたあとだということがわかります。
これも単純に素数の倍数をふるい落としてもいいのですが、
無駄な作業が減るので効率化出来ます。

以上でございます。