埃拉托斯特尼筛法

Sieve of Eratosthenes（埃拉托斯特尼筛法）是一种古老且有效的算法，用于找出一定范围内所有的质数。这个名字来源于古希腊的数学家埃拉托斯特尼，他在公元前3世纪提出了这个算法。 埃拉托斯特尼筛法的基本思想是从最小的质数开始，逐步筛选掉其倍数，剩下的就是质数。以下是该算法的步骤：

1. 创建一个列表，包含从2开始到你想找到的最大数 $ n $ 的所有整数。
2. 选择列表中的第一个数（它是2，是唯一的偶数质数），然后将其所有的倍数（除了它自己）标记为非质数。
3. 找到列表中的下一个未被标记的数，它是下一个质数，然后重复步骤2，将其所有的倍数标记为非质数。
4. 继续这个过程，直到你到达列表的末尾。
5. 在这个过程中未被标记的数就是质数。 以下是埃拉托斯特尼筛法的伪代码示例：

   function SieveOfEratosthenes(n)
       create a list "prime[0..n]" and initialize all entries as true.
       A value in prime[i] will finally be false if i is Not a prime, else true bool prime[n+1];
       memset(prime, true, sizeof(prime));
       for p = 2 to sqrt(n)
           if prime[p] is true
               for i = p*p to n step p
                   prime[i] = false
       for p = 2 to n
           if prime[p] is true
               print p

   埃拉托斯特尼筛法的时间复杂度是 $ O(n n) $，这使得它非常适用于寻找小于一百万或更大的范围内的所有质数。尽管这个算法在处理非常大的数字时效率不是最高的，但它因其简单性和易于实现而广受欢迎。

def sieve_of_eratosthenes(n):
    # 初始化一个布尔数组，所有的值都设为True
    prime = [True for _ in range(n+1)]
    p = 2
    while (p * p <= n):
        # 如果prime[p]没有被改变，那么它是一个质数
        if prime[p] == True:
            # 更新所有p的倍数为非质数
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1

    # 收集所有质数
    primes = []
    for p in range(2, n):
        if prime[p]:
            primes.append(p)
    return primes

# 示例：找出小于30的所有质数
print(sieve_of_eratosthenes(30))