素数筛法

什么是素数？

素数是指只能被1和它本身整除的数。例如：2、3、5、7、11、13 都是素数。而像 4、6、8、9 就不是素数，因为它们可以被其他数字整除。

1. 试除法

推导过程：

试除法是最直观的一种判断素数的方法。对于一个数 ( n )，我们通过逐个尝试从 2 到 ( \sqrt{n} ) 的所有整数，检查是否能整除。如果能整除，那么 ( n ) 就不是素数；如果不能整除，那么 ( n ) 就是素数。

推导：

• 如果一个数 ( n ) 是合数，它至少有两个小于或等于 ( \sqrt{n} ) 的因数。举个例子：36 是合数，它的因数有 2、3、4、6、9、12、18。最小的因数是 2，最大的是 18，( \sqrt{36} = 6 )，所以我们只需要检查从 2 到 6 的因数即可。

判断过程：

例如判断 13 是否为素数：

• 13 是否能被 2 整除？不行（13 ÷ 2 = 6.5）。
• 13 是否能被 3 整除？不行（13 ÷ 3 = 4.33）。
• 13 是否能被 4 整除？不行（13 ÷ 4 = 3.25）。
• 13 没有被 2、3、4 整除，所以 13 是素数。

2. 埃氏筛法（Sieve of Eratosthenes）

推导过程：

埃氏筛法是一种更高效的筛选素数的方法。其思想是从 2 开始，逐个标记出每个素数的倍数，直到不再有新的倍数。最终，未被标记的数就是素数。

推导：

1. 从 2 开始，假设所有数都是素数。
2. 从 2 开始标记出 2 的倍数（除了 2 本身，其他都是合数）。
3. 然后找到下一个未标记的数 3，标记出 3 的倍数。
4. 继续这个过程，直到最大值 ( n )。
5. 最后，所有未被标记的数就是素数。

示例：

例如找 1 到 20 之间的素数：

1. 初始化：假设所有数都是素数。
2. 标记 2 的倍数：2, 4, 6, 8, 10, 12, 14, 16, 18, 20。
3. 标记 3 的倍数：3, 6, 9, 12, 15, 18。
4. 标记 5 的倍数：5, 10, 15, 20。
5. 标记 7 的倍数：7, 14。

最终，剩下的未标记数就是素数：2, 3, 5, 7, 11, 13, 17, 19。

推导结果：

通过这一筛选过程，我们最终找到了 1 到 20 之间的素数：[2, 3, 5, 7, 11, 13, 17, 19]。

3. 线性筛法（Linear Sieve）

推导过程：

线性筛法的关键在于：每当我们找到一个新的素数时，我们只标记它的倍数。这样避免了埃氏筛法中重复标记的情况，从而提高了效率。

推导：

1. 初始化：假设所有数都是素数。
2. 从小到大遍历每个数 ( i )：
   • 如果 ( i ) 是素数（即它没有被标记过），则把它加入素数列表。
   • 标记 ( i ) 的倍数为合数，但要注意，只标记 ( i ) 和它之后的倍数，避免重复标记。
3. 重复这个过程直到最大值 ( n )。

示例：

例如找 1 到 20 之间的素数：

1. 初始化：假设所有数都是素数。
2. 从 2 开始，2 是素数，标记它的倍数：2, 4, 6, 8, 10, 12, 14, 16, 18, 20。
3. 找到下一个素数 3，标记它的倍数：3, 6, 9, 12, 15, 18。
4. 找到下一个素数 5，标记它的倍数：5, 10, 15, 20。
5. 找到下一个素数 7，标记它的倍数：7, 14。
6. 不需要继续，最终得到素数：2, 3, 5, 7, 11, 13, 17, 19。

通过这种方法，我们避免了重复标记，效率更高。

推导结果：

最终，1 到 20 之间的素数：[2, 3, 5, 7, 11, 13, 17, 19]。

4. 总结

• 试除法：从 2 开始，逐个检查是否能整除，简单但效率低。
• 埃氏筛法：假设所有数都是素数，从小到大逐个标记素数的倍数，效率较高。
• 线性筛法：避免重复标记，进一步提高了效率，特别适用于处理大范围的素数。

欧拉筛法

欧拉筛法（Euler’s Sieve）是一种改进的筛法，用来找出素数，尤其适用于大范围内素数的筛选。它与线性筛法类似，但它采用不同的标记方式，避免了对某些倍数的重复标记，并且具有更高的效率。

推导过程：

欧拉筛法基于以下的观察：当你筛选素数时，每次找到一个新的素数 ( p )，你就将它与已有的所有数的倍数进行标记，但 欧拉筛法避免重复标记。它的核心思想是基于素数分解的方法，避免了不必要的计算。

步骤：

1. 初始化： 假设从 2 开始，所有数都是素数。

2. 从小到大遍历每个数 ( i )：

   • 如果 ( i ) 是素数（即它没有被标记过），则它加入素数列表。
   • 对于每个已知的素数 ( p )，如果 ( i \times p ) 小于等于最大值 ( n )，则将 ( i \times p ) 标记为合数。
   • 但关键在于，当标记 ( i \times p ) 时，如果 ( i ) 是素数，只标记 ( p ) 的倍数，并且从小到大的顺序标记，避免重复标记。

3. 停止条件： 直到处理完所有数。

示例：

我们以找 1 到 20 之间的素数为例：

1. 初始化：假设所有数都是素数：[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]（其中 True 表示素数，False 表示合数）。

2. 开始筛选：

   • 从 2 开始：标记 2 的倍数为合数：2, 4, 6, 8, 10, 12, 14, 16, 18, 20。
   • 到 3：标记 3 的倍数为合数：3, 6, 9, 12, 15, 18。
   • 到 5：标记 5 的倍数为合数：5, 10, 15, 20。
   • 到 7：标记 7 的倍数为合数：7, 14。

3. 最终结果： 经过筛选，剩下的素数是：[2, 3, 5, 7, 11, 13, 17, 19]。

优化与特点：

• 欧拉筛法和线性筛法类似，但它的优势在于：当我们用一个已知的素数 ( p ) 来标记倍数时，避免了重复标记的情况。
• 它的时间复杂度与线性筛法相似，但有时在处理某些情况时，它的标记过程更加简洁高效。

示例代码，找出 1 到 20 之间的素数：

def euler_sieve(n):
    # 初始化一个布尔数组，True表示素数，False表示合数
    is_prime = [True] * (n + 1)
    primes = []
    
    for i in range(2, n + 1):
        if is_prime[i]:  # i 是素数
            primes.append(i)
        # 标记 i 的倍数为合数
        for p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False
            if i % p == 0:  # 避免重复标记
                break

    return primes

# 测试：找出 1 到 20 之间的素数
print(euler_sieve(20))

解释：

1. 初始化一个布尔数组 is_prime，其中 True 表示数字是素数，False 表示数字是合数。
2. 通过遍历从 2 到 n 的所有数字，检查哪些是素数。
3. 对每个发现的素数 i，标记它的倍数为合数。只标记小于或等于 n 的倍数。
4. 通过循环 for p in primes，如果 i * p 超过 n，就停止标记，确保不会重复标记倍数。

输出：

[2, 3, 5, 7, 11, 13, 17, 19]

这就是 1 到 20 之间的素数，经过欧拉筛法筛选出来的结果。

总结：

欧拉筛法是一种比埃拉筛法更高效的筛法，适合在计算机程序中处理较大范围的素数。通过优化标记方式，它能够避免不必要的重复操作，进一步提高筛选素数的效率。