埃拉托斯特尼筛法

发表于

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

  1. 创建一个列表，包含从2开始到你想找到的最大数 $ n $ 的所有整数。
  2. 选择列表中的第一个数（它是2，是唯一的偶数质数），然后将其所有的倍数（除了它自己）标记为非质数。
  3. 找到列表中的下一个未被标记的数，它是下一个质数，然后重复步骤2，将其所有的倍数标记为非质数。
  4. 继续这个过程，直到你到达列表的末尾。
  5. 在这个过程中未被标记的数就是质数。
    以下是埃拉托斯特尼筛法的伪代码示例：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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 \log \log n) $，这使得它非常适用于寻找小于一百万或更大的范围内的所有质数。尽管这个算法在处理非常大的数字时效率不是最高的，但它因其简单性和易于实现而广受欢迎。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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))