Python学習日記 – 素数判定
はじめに
ある数が素数かどうかを判定する一般的な方法は、2、5、7、11、13、17 で試し割りすることですが、この方法は1000以下の数に対してのみ高い精度を持ちます。そこで、絶対に正しく、かつPythonの他のモジュールを使わない素数判定方法はないかと考えました。Pythonの数学モジュールを使えば素数判定は簡単になりますが、モジュールを導入するのは少し冗長に思えます。
一般的なアルゴリズム
print("素数の概念は、1とそれ自身でのみ割り切れる数字です。\nここでは、入力した数字が素数かどうかを計算します。")
while True:
number = input("数字を入力してください:")
number = int(number)
if number == 2:
print("素数です")
elif number == 3:
print("素数です")
elif number == 5:
print("素数です")
elif number == 7:
print("素数です")
elif number == 11:
print("素数です")
elif number == 17:
print("素数です")
elif number == 13:
print("素数です")
elif number == 19:
print("素数です")
else:
if number % 2 == 0:
print("\tこの数は2で割り切れるため、素数ではありません。")
else:
if number % 3 == 0:
print("\tこの数は3で割り切れるため、素数ではありません。")
else:
if number % 5 == 0:
print("\tこの数は5で割り切れるため、素数ではありません。")
else:
if number % 7 == 0:
print("\tこの数は7で割り切れるため、素数ではありません。")
else:
if number % 11 == 0:
print("\tこの数は11で割り切れるため、素数ではありません。")
else:
if number % 13 == 0:
print("\tこの数は13で割り切れるため、素数ではありません。")
else:
if number % 17 == 0:
print("\tこの数は17で割り切れるため、素数ではありません。")
else:
if number % 19 == 0:
print("\tこの数は19で割り切れるため、素数ではありません。")
else:
print("素数です")
全部で46行のコードで、非常に短時間で素数かどうかを判定できますが、このアルゴリズムは正確ではありません!

図のように、5773という数字を入力すると、少なくとも23、251、5773、1の4つの数で割り切れますが、アルゴリズムは素数と表示するため、このアルゴリズムは正確ではありません。
しかし、このアルゴリズムの利点は、すぐに結論が得られ、CPUの計算リソースをあまり消費しないことです。
高度なアルゴリズム
絶対に素数を判定できる計算方法があります。
数nが素数かどうかを判定するとき、1からnまでのすべての数でnを割り、割り切れるかどうかを調べます。割り切れる回数が2より多ければ、1とn自身以外にも割り切れる数が存在することになり、素数の概念に反するため、nは素数ではありません。逆に、割り切れる回数が2以下なら素数です。
print("注意:最終結果の表示時間はCPUの性能と入力する数に依存します\n1000万以下の数字を推奨します。大きすぎる数字は短時間で結果を出せません")
x = int(input('数値を入力:'))
z = 0
for i in range(1,x+1):
if x % i == 0:
z = z+1
if z > 2:
print("素数ではありません")
else:
print("素数です")
これは高度なアルゴリズムで、Python自体のコードと関数を使って処理を行います。計算結果は100%正確ですが、唯一の欠点は総当たり法を使用しているため、非常に大きな数の場合、短時間で結果を得ることができず、CPUの膨大な計算リソースを消費することです。
アルゴリズム思考の構築
一般的なアルゴリズム

図には単純な思考プロセスしか示されていませんが、実際にはこのように類推していきます。7、11、13、17、23などでも割り続けることができます。
高度なアルゴリズム

これはほぼ完璧な方法です。
コード分析
はじめに
今回のコード分析では、すでに説明したアルゴリズムを多用しているため、組み込み関数2つのみを分析します。
int() を使用した数値変換
int() 関数は高度なアルゴリズムで使用されています。int() を input() とネストすることで、変換のためのコードを1行追加する必要がありません。その機能は float() 関数と似ていますが、数値を浮動小数点数に変換するのではなく、実数に変換します。
a = "2"
b = int(a)
print(b)
c = b+1
print(b)
print(c)
簡単な例で、float() 関数との違いがわかります。
実行結果は次のようになります。
2
2
3
小数点や小数点以下の数は含まれません。
range() を使用した数の生成
非常に簡単な関数で、Python range() 関数の使い方 | 菜鳥教程 で詳しく学べます。
ここでは簡単な例を1つ挙げます。
for a in range(1,10):
print(a)
出力結果
1
2
3
4
5
6
7
8
9
終わりに
素数アルゴリズムの研究は、私がアルゴリズム研究を始める第一歩でした。今後も少しずつ進歩していきます!