萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 素數判斷演算法:試除法實作與優化方向

基本試除法


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),僅適合極小數值教學。

優化 1:只檢查至 √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)。

優化 2:跳過偶數


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

進階:Miller-Rabin 概率檢測 (大數適用)


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⁻¹⁰。

標準庫支援 (Python 3.8+)


import math
math.isprime(n)  # 內建高效實作

總結建議

  • 教學/小數:試除法至 √n + 跳過偶數
  • 生產/大數:math.isprime 或 Miller-Rabin
  • 批量篩選:埃拉托斯特尼篩法 (Sieve of Eratosthenes)
copyright © 萬盛學電腦網 all rights reserved