建站
咨詢
售后
建站咨詢
新聞中心
在Python中，我們可以使用多種方法來判斷一個數(shù)是否為質(zhì)數(shù)，下面是一些常用的方法：
10年積累的網(wǎng)站設(shè)計、做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有滄源免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。
1、試除法：從2開始，一直到這個數(shù)的平方根，看看這個數(shù)能否被其中任何一個數(shù)整除，如果能，那么這個數(shù)就不是質(zhì)數(shù)；如果不能，那么這個數(shù)就是質(zhì)數(shù)。
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
2、埃拉托斯特尼篩法：首先創(chuàng)建一個布爾值列表，表示每個數(shù)是否為質(zhì)數(shù)，然后從2開始，將2的倍數(shù)標記為非質(zhì)數(shù)，然后找到下一個未被標記的數(shù)，將其倍數(shù)標記為非質(zhì)數(shù)，重復(fù)這個過程，直到遍歷完整個列表，列表中值為True的索引對應(yīng)的數(shù)就是質(zhì)數(shù)。
def eratosthenes_sieve(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
return [x for x in range(n + 1) if primes[x]]
3、MillerRabin素性檢驗：這是一個概率算法，用于判斷一個大數(shù)是否為質(zhì)數(shù)，它的基本思想是：如果一個數(shù)n是合數(shù)，那么它可以表示為a*b（a和b都是小于等于sqrt(n)的正整數(shù)），那么對于任意一個小于n的正整數(shù)a，都有以下兩個性質(zhì)：
a^(n1) ≡ 1 (mod n) 如果a^(n1) 1能被n整除，那么n就不是質(zhì)數(shù)。
a^d * b^e ≡ 1 (mod n) 如果存在d、e使得a^d * b^e 1能被n整除，那么n就不是質(zhì)數(shù)。
import random
def miller_rabin(n, k=5): # number of tests to run
if n < 6: # insecure for small numbers!
return [False, False, True, True, False, True][n] # timing attack resistant
if n & 1 == 0: # even numbers other than 2 are not primes
return False
r, s = 0, n 1
while s % 2 == 0:
r += 1
s //= 2
for _ in range(k):
a = random.randrange(2, n 1)
x = pow(a, s, n) # compute a^s % n using modular exponentiation
if x == 1 or x == n 1:
continue
for r in range(1, r): # try r times to find a nontrivial square root of x
x = pow(x, 2, n) # compute x^2 % n using modular exponentiation
if x == n 1:
break else:
continue
else: # this means we've failed to find a nontrivial square root of x within r tries
return False # composite number detected! return false and stop testing further.
return True # passed all k tests! probably```
以上就是Python中判斷質(zhì)數(shù)的幾種常用方法，需要注意的是，這些方法并不是絕對準確的，它們都有一定的概率誤差，試除法和埃拉托斯特尼篩法的時間復(fù)雜度較低，但可能會漏掉一些質(zhì)數(shù)；而MillerRabin素性檢驗雖然時間復(fù)雜度較高，但準確性更高，在實際使用時，可以根據(jù)需要選擇合適的方法。
當前文章：python中如何判斷質(zhì)數(shù)
文章來源：http://www.5511xx.com/article/copiiej.html
