【Python判斷素數技巧】輕鬆識別任意數字是否為質數，揭秘高效演算法與實例解析

質數的定義

質數（Prime Number），又稱為素數，是指在大年夜於1的天然數中，除了1跟它本身以外不再有其他因數的數。比方，2、3、5、7、11等都是質數。

斷定質數的方法

斷定一個數能否為質數，有多少種常用的方法：

1. 直接羅列法

直接羅列法是最直不雅的方法，即從2開端壹壹試除，直到該數的平方根。假如在這個範疇內能找到一個數能整除該數，則該數不是質數。

import math

def is_prime_enum(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

2. 篩法

篩法是一種更高效的斷定質數的方法。常用的篩法有埃拉托斯特尼篩法（Sieve of Eratosthenes）。

def sieve_of_eratosthenes(n):
    prime = [True for _ in range(n + 1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    prime[0], prime[1] = False, False
    return [p for p in range(n + 1) if prime[p]]

3. 利用math庫

Python中的math庫供給了一個isqrt函數，可能疾速打算整數的平方根，從而進步斷定質數的效力。

import math

def is_prime_math(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

實例剖析

以下是一個實例，展示怎樣利用這些方法斷定一個數字能否為質數。

number = 29

# 直接羅列法
print(f"直接羅列法斷定{number}能否為質數：{is_prime_enum(number)}")

# 篩法
primes = sieve_of_eratosthenes(100)
print(f"篩法斷定{number}能否為質數：{number in primes}")

# 利用math庫
print(f"利用math庫斷定{number}能否為質數：{is_prime_math(number)}")

以上三種方法各有優毛病，直接羅列法簡單易懂，但效力較低；篩法實用於生成一定範疇內的全部質數，效力較高；利用math庫可能進步斷定單個質數的效力。在現實利用中，可能根據須要抉擇合適的方法。