def is_prime(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
時間複雜度 O(n),僅適合極小數值教學。
若 n = a × b,則 a ≤ √n 或 b ≤ √n。
import math
def is_prime(n):
if n < 2:
return False
for i in range(2, int(math.isqrt(n)) + 1): # Python 3.8+ math.isqrt
if n % i == 0:
return False
return True
複雜度 O(√n)。
def is_prime(n):
if n < 2: return False
if n == 2: return True
if n % 2 == 0: return False
for i in range(3, int(math.isqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
import random
def is_probable_prime(n, k=10):
if n < 2: return False
small_primes = [2,3,5,7,11,13,17,19,23,29]
for p in small_primes:
if n % p == 0:
return n == p
# 寫入 n-1 = d * 2^s
d, s = n-1, 0
while d % 2 == 0:
d //= 2
s += 1
for _ in range(k):
a = random.randrange(2, n-1)
x = pow(a, d, n)
if x == 1 or x == n-1:
continue
for _ in range(s-1):
x = pow(x, 2, n)
if x == n-1:
break
else:
return False
return True
適用於大整數 (如 RSA 金鑰生成),k=10 錯誤率 < 4⁻¹⁰。
import math
math.isprime(n) # 內建高效實作
math.isprime 或 Miller-Rabin