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 這四個數整除，但是算法顯示，是素數，因此這個算法是不準確的。

但是這個算法有個好處就是，可以很快的得出結論，是不需要消耗多少 CPU 算力的。

高階算法#

我們知道有一種絕對是素數的計算方法。

在判斷一個數 n 是否是素數時，我們可以用從 1 到 n 的所有數，挨個去除 n 得到是否整除，如果整除的次數大於 2 就意味著除了 1 和 n 本身外，存在其它數可以整除它，就違背了素數的概念，意味著這個 n 就不是素數，反之是素數。

print("提示：最終結果的顯示時間取決與CPU的算力和你輸入的數大小\n建議輸入一千萬以下的數字，數字太大無法在短時間內得出結果")
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 之類的。

高階算法

這是一個近乎完美的方法

代碼分析#

前言#

此次代碼分析由於大量使用已經講過的算法，因此僅分析兩個內置函數。

使用 `int()` 進行數字轉換#

int() 函數在高階算法中有使用，我們使用 int() 於 input() 嵌套，不必再多寫一行代碼來轉換，其作用和 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