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 は素数ではなく、逆に素数であることを意味します。

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)

出力結果

尾声#

素数アルゴリズムの研究は、私がアルゴリズム研究を始める第一歩です。今後、徐々に進歩していくでしょう！

この記事は Mix Space によって xLog に同期更新されています。原始リンクは https://fmcf.cc/posts/technology/Python_Notes_5