Python 埃拉托色尼筛法 – 寻找质数

在本文中，我们将介绍如何使用Python实现埃拉托色尼筛法来寻找质数。

阅读更多：Python 教程

什么是埃拉托色尼筛法？

埃拉托色尼筛法是一种用于筛选质数的古老算法。它的原理很简单：先列出从2开始的所有正整数，然后从2开始，将它的倍数都筛除（标记为非质数），接着找到下一个未被筛除的数，重复这个过程，直到所有的数都已被筛除。

实现埃拉托色尼筛法

下面是一个使用Python实现埃拉托色尼筛法的示例代码：

def sieve_of_eratosthenes(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False

    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n+1, p):
                primes[i] = False
        p += 1

    return [i for i, is_prime in enumerate(primes) if is_prime]

n = 100
prime_numbers = sieve_of_eratosthenes(n)
print(prime_numbers)

在上面的代码中，我们首先创建一个长度为n+1的布尔列表primes，用于记录每个数是否为质数。然后对2到√n的数进行遍历，如果当前数为质数，则将其倍数都标记为非质数。最后，我们返回所有为质数的数。

在上述示例中，我们将n设定为100，然后打印出从2到100之间的所有质数。

运行上述代码，输出结果为：[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]。这些数都是从2到100之间的质数。

优化性能

虽然上述代码已经能够正确地找出质数，但对于较大的数，性能可能不够高。下面是一些优化策略：

1. 在标记数的倍数时，可以跳过偶数。因为除了2以外，其他偶数都不可能是质数。
2. 可以只对奇数进行标记，循环时步长设为2。
3. 对于大于√n的数，不需要进行标记。

下面是经过优化的实现示例代码：

def sieve_of_eratosthenes(n):
    if n < 2:
        return []

    primes = [True] * ((n+1)//2)
    primes[0] = False

    p = 3
    while p * p <= n:
        if primes[p // 2]:
            for i in range(p * p, n+1, 2 * p):
                primes[i // 2] = False
        p += 2

    return [2] + [2 * i + 1 for i, is_prime in enumerate(primes) if is_prime]

n = 100
prime_numbers = sieve_of_eratosthenes(n)
print(prime_numbers)

在上述代码中，我们首先创建一个长度为(n+1)//2的布尔列表primes，每个索引i对应的数为2*i+1。然后对3到√n的奇数进行遍历，如果当前数为质数，则将其奇数倍数都标记为非质数。最后，我们返回[2]加上所有为质数的数。

运行以上经过优化的代码，输出结果仍然为：[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]。

总结

本文介绍了如何使用Python实现埃拉托色尼筛法来寻找质数。埃拉托色尼筛法是一种高效的算法，能够快速筛选出所有质数。我们还对代码进行了优化，使其在处理大数时能够更快地找出质数。通过学习和应用这个算法，我们可以更好地理解埃拉托色尼筛法的原理和实现。希望本文对你学习和使用Python实现埃拉托色尼筛法有所帮助！