前言#
数が素数であるかどうかを判断する一般的な方法は、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 は素数ではありません。逆に、素数です。
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()関数は高階アルゴリズムで使用されており、input()にネストしてint()を使用することで、変換のために別の行を書く必要がありません。その機能はfloat()関数に似ていますが、数字を浮動小数点数に変換するのではなく、実際の数になります。
a = "2"
b = int(a)
print(b)
c = b+1
print(b)
print(c)
簡単な例で、float()関数との違いがわかります。
実行結果は次のようになります。
2
2
3
小数点や小数点以下の数は含まれていません。
range()を使用して数を生成#
非常に簡単な関数で、Python range () 関数用法 | 菜鸟教程で具体的に学ぶことができます。
ここでは簡単な例を挙げます。
for a in range(1,10):
print(a)
出力結果
1
2
3
4
5
6
7
8
9
尾声#
素数アルゴリズムの研究は、私がアルゴリズム研究を始める第一歩です。今後、徐々に進歩していくつもりです！
この記事は Mix Space によって xLog に同期更新されています。
元のリンクは https://fmcf.cc/posts/technology/Python_Notes_5