banner
Magneto

Magnetoの小屋

Magneto在區塊鏈上の小屋,讓我們的文章在互聯網上永遠熠熠生輝!!

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 行代碼,可以在極短時間內,判斷一個數是否為素數,但是這個算法,是不準確的!

image

如圖,我們輸入 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 的巨大算力去運算才行。

算法思維構建#

常規算法

image

圖上僅顯示了一個簡單的思維過程,其實是以此類推的,我們可以繼續除 7、11、13、17、23 之類的。

高階算法

image

這是一個近乎完美的方法

代碼分析#

前言#

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

使用 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)

輸出結果

1
2
3
4
5
6
7
8
9

尾聲#

素數算法的研究,是我開始算法研究邁出的第一步,以後會慢慢進步的!

此文由 Mix Space 同步更新至 xLog
原始鏈接為 https://fmcf.cc/posts/technology/Python_Notes_5


載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。