python素数筛选法浅析

下面是详细讲解“Python素数筛选法浅析”的完整攻略。

1. 什么是素数筛选法？

素数筛选法是一种用于筛选素数的算法，其基本思想是从小到大枚举每个数，如果这个数是素数，则将其所有的倍数标记为合数，直到枚举完所有的数。

2. Python素数筛选法的实现

下面是Python实现素数筛选法的示例：

def sieve_of_eratosthenes(n):
    """
    素数筛选法
    :param n: 筛选范围
    :return: 所有素数的列表
    """
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False
    return [i for i in range(n + 1) if primes[i]]

上述代码中，定义了一个名为sieve_of_eratosthenes的函数，该函数接受一个参数n，表示筛选范围。首先，创建一个长度为n+1的布尔类型列表primes，用于标记每个数是否为素数。将primes[0]和primes[1]标记为False，因为0和1不是素数。然后，从2开始枚举每个数，如果这个数是素数，则将其所有的倍数标记为合数。最后，返回所有素数的列表。

下面是使用sieve_of_eratosthenes函数计算100以内的素数的示例：

primes = sieve_of_eratosthenes(100)
print(primes)

输出结果为：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

3. 总结

素数筛选法是一种用于筛选素数的算法，其基本思想是从小到大枚举每个数，如果这个数是素数，则将其所有的倍数标记为合数，直到枚举完所有的数。Python中，可以使用函数实现素数筛选法，代码简单易懂，效率较高。