Python如何表示素数

素数，又称质数，是指在大于1的自然数中，除了1和自身，没有其他因数的数。在数学中，素数具有重要的地位，也是算法和密码学等领域的基础。在Python中，我们可以通过以下几种方式来表示素数。

一、直接判断法

直接判断法是最基本的判断素数的方法，即对于给定的自然数n，判断n是否能被2到$sqrt{n}$之间的素数整除，如果能，那么n就不是素数；否则，n就是素数。


import math

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

在这段代码中，我们首先判断n是否小于等于1，若是，则返回False；然后使用一个循环从2到$sqrt{n}$进行遍历，判断n是否能被这些数整除；如果能，则返回False，说明n不是素数；否则，返回True，说明n是素数。

二、埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种筛选法，通过不断的筛选和剔除，来找出一定范围内的所有素数。步骤如下：

1）创建一个长度为n+1的布尔型列表is_prime，初始值都为True。

2）从2开始遍历到$sqrt{n}$：

a. 对于is_prime[i]为True的整数i，将i的倍数(2i, 3i, 4i, ...)，在is_prime中标记为False。
b. 如果is_prime[i]为True，说明i是素数，将其加入到素数列表中。


def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    primes = []
    
    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
    
    return primes

在这段代码中，首先创建一个长度为n+1的布尔型列表is_prime，并将所有的值初始化为True。然后从2到$sqrt{n}$进行遍历，对于每个is_prime为True的整数i，将i的倍数在is_prime中标记为False。最后，将is_prime中为True的索引加入到素数列表primes中，并返回该列表。

三、Miller-Rabin素性测试

Miller-Rabin素性测试是一种概率性的素数判定算法，可以高效地判断一个数是否是素数。步骤如下：

1）将待判断的数n-1表示为$2^s cdot t$的形式，其中t是奇数。

2）选择一个范围在[2, n-1]之间的随机整数a。

3）计算$b_0 = a^t mod n$，如果$b_0 equiv pm 1 (mod n)$，则n可能是素数。

4）重复k次，计算$b_i = (b_{i-1})^2 mod n$，如果$b_i equiv 1 (mod n)$，则n是合数；若$b_i equiv -1 (mod n)$，则n可能是素数。


import random

def miller_rabin(n, k):
    if n == 2 or n == 3:
        return True
    if n == 1 or n % 2 == 0:
        return False
    
    s, t = 0, n - 1
    while t % 2 == 0:
        s += 1
        t //= 2
    
    for _ in range(k):
        a = random.randint(2, n - 1)
        b = pow(a, t, n)
        if b == 1 or b == n - 1:
            continue
        for _ in range(s - 1):
            b = b * b % n
            if b == n - 1:
                break
        else:
            return False
    
    return True

在这段代码中，我们首先对特殊情况进行处理，如果n等于2或3则直接返回True，如果n等于1或者为偶数则返回False。然后将n-1表示为$2^s cdot t$的形式，其中t是奇数。接着进行k次测试，每次选择一个范围在[2, n-1]之间的随机整数a，判断$b_i = (b_{i-1})^2 mod n$是否满足$b_i equiv pm 1 (mod n)$的条件。如果所有的测试都通过，则n可能是素数。

四、结语

通过直接判断法、埃拉托斯特尼筛法和Miller-Rabin素性测试，我们可以在Python中有效地表示素数。这些方法可以根据不同的需求和场景进行选择，以满足我们对素数的具体要求。在实际应用中，我们可以根据具体情况，选择适合的方法来判断和处理素数。