用Python实现素数相关算法并做注释说明

当谈论素数相关算法时，以下是几个常见的算法，包括素数检测和生成素数序列。我将为你提供 Python 代码示例，并添加注释说明。

素数检测算法

方法一：试除法

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

注释说明：

is_prime 函数用于检测一个数是否为素数。

首先判断数是否小于 2，小于 2 的数都不是素数。

从 2 开始到平方根（取整）之间的数逐个试除，如果能整除，则不是素数，返回 False。

若循环结束仍然没有找到能整除的数，则说明是素数，返回 True。

方法二：Miller-Rabin 算法

import random

def is_prime(num, k=5):
    if num < 2:
        return False
    if num in (2, 3):
        return True
    if num % 2 == 0:
        return False

    def check(a, s, d, n):
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            return True
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                return True
        return False

    s, d = 0, num - 1
    while d % 2 == 0:
        s += 1
        d //= 2

    for _ in range(k):
        a = random.randint(2, num - 2)
        if not check(a, s, d, num):
            return False
    return True

注释说明：

is_prime 函数使用 Miller-Rabin 算法进行素数检测。

首先判断数是否小于 2，小于 2 的数都不是素数。

若数为 2 或 3，则为素数。

若数为偶数，则不是素数。

通过循环将数表示为 d * 2^s + 1 的形式。

对于给定的 k 值（默认为 5），选择 k 个随机数 a 进行检测。

check 函数用于执行 Miller-Rabin 算法的检测步骤，如果 a 的次方满足一定条件，则可能是素数。

若所有的随机数都通过检测，则返回 True，否则返回 False。

生成素数序列算法

方法一：埃拉托斯特尼筛法

def generate_primes(limit):
    primes = [True] * (limit + 1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= limit:
        if primes[p]:
            for i in range(p * p, limit + 1, p):
                primes[i] = False
        p += 1
    prime_numbers = [num for num, is_prime in enumerate(primes) if is_prime]
    return prime_numbers