在 Python 中檢查數字是否為質數
素數可以被描述為一個自然數,除了數字 1 和它本身之外,沒有其他正除數。數 1 不計入素數列表。
本教程將討論可用於檢查數字是否為質數的不同方法。
在 Python 中使用簡單迭代法確定質數
在這個方法中,我們使用一個簡單的迭代方法,使用 for
或 while
迴圈。遍歷從 2 開始一直到 K/2
的數字,並檢查這些數字中是否有任何一個能除以 K
。
如果找到符合此條件的數字,則返回 False
。另一方面,如果所有數字都不符合此標準,則給定數字 K
是素數,並返回 True
值。
下面的程式碼使用簡單的迭代方法來檢查給定的數字是否是 Python 中的質數。
k = 13
# 1 not being a prime number, is ignored
if k > 1:
for i in range(2, int(k/2)+1):
if (k % i) == 0:
print("It is not a prime number")
break
else:
print("It is a prime number")
else:
print("It is not a prime number")
輸出:
It is a prime number
你可以通過應用一些更改來優化上面的程式碼。進行以下優化以使程式碼更快:
*檢查直到達到給定數字的根,而不是檢查確切的數字。這個過程基本上消除了當數字 K
的較大因數是已經迭代過的較小因數的倍數時出現的冗餘。
*所有素數都以 6n±1 的形式存在,只有 2 和 3 是例外。因此,檢查給定數與 2 和 3 的整除性,然後檢查每個具有 6n±1 形式的數是更有效的解決方案。
下面的程式碼使用優化的簡單迭代方法來檢查給定的數字是否是 Python 中的質數。
def isitPrime(k):
if k==2 or k==3: return True
if k%2==0 or k<2: return False
for i in range(3, int(k**0.5)+1, 2):
if k%i==0:
return False
return True
print(isitPrime(13))
輸出:
True
優化的迭代方法使其比簡單的迭代方法更快、更高效約 30%。
使用 sympy.isprime()
函式檢查給定數是否是 Python 中的素數
SymPy
是 Python 中的一個庫,用於實現符號數學。它旨在成為一個包含所有基本功能的簡單計算機代數系統 (CAS)。此方法需要安裝此模組,只需使用 pip
命令即可下載。
sympy.isprime()
是 SymPy
模組下的內建函式,可用於檢查可能的素數。它是一個直接函式,如果要檢查的數字是素數,則返回 True
,如果要檢查的數字不是素數,則返回 False
。
下面的程式碼使用 sympy.isprime()
函式來檢查給定的數字是否是 Python 中的素數。
from sympy import *
isprime(8)
isprime(11)
輸出:
False
True
我們應該注意,任何負數都不屬於素數的標準。如果針對它檢查任何負數,這些函式的輸出可能會有所不同。
Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.
LinkedIn