前言#
對於一個數是否為素數,常規的方法就是 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)
輸出結果
1
2
3
4
5
6
7
8
9
尾聲#
素數算法的研究,是我開始算法研究邁出的第一步,以後會慢慢進步的!
此文由 Mix Space 同步更新至 xLog
原始鏈接為 https://fmcf.cc/posts/technology/Python_Notes_5