@TOC

前言

在学习数学的过程中，质数是一个非常重要的概念。质数不仅是所有整数的基石，还在许多数学问题和实际应用中扮演着关键角色。为了高效地找出一系列数字中的所有质数，我们可以使用一种叫做质数筛的方法。质数筛是一个聪明的数学工具，帮助我们迅速识别出质数，并筛除非质数。本文将介绍质数筛的基本原理以及它的一些优化方法，让我们能够更加高效地找到质数。

质数筛介绍

质数筛是一种找出所有质数的方法，就像用一个筛子来筛掉一些东西，我们用质数筛来“筛掉”所有不是质数的数字，只留下质数。

质数是什么？

质数是只能被1和它自己整除的数，比如2、3、5、7、11、13等等。质数不能被其他的数字整除。

质数筛的基本思路

我们用一个叫“质数筛”的方法来找到一定范围内的所有质数。这个方法就像是用筛子从很多数字中筛选出质数。

举个例子：

假设我们要找出小于20的所有质数。

1. 列出所有小于20的数字：

   2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
   

2. 从最小的质数开始筛：

   • 先从2开始，因为2是第一个质数。我们用2去除掉所有2的倍数（4、6、8、10、12、14、16、18）。

   剩下的数字：

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

3. 然后是下一个质数3：

   • 用3去除掉所有3的倍数（9、15）。注意3和它自己是质数，我们不会去除3。

   剩下的数字：

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

4. 继续下一个质数：

   • 继续用下一个质数去除掉它的倍数（在这个范围内是5、7、11、13、17、19）。

   最后剩下的质数：

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

5. 结束筛选：

   • 现在我们已经找出了小于20的所有质数。

总结：

质数筛就是一个用来找质数的“筛子”。我们从最小的质数开始，逐步去除掉所有不是质数的数字，最后留下的就是我们想要的质数。这种方法简单而有效，特别适合用来找出一段范围内的所有质数。

埃氏筛法

埃拉托斯特尼筛法是一种找出所有质数的聪明方法，它就像一个特别的筛子，可以帮助我们把所有的非质数“筛掉”，只留下质数。这个方法很简单，适合小朋友们理解。

埃拉托斯特尼筛法的步骤

1. 准备一个数字列表：
   首先，我们列出一串从1开始的数字，比如小于30的数字：

   2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29
   

2. 从最小的质数开始：

   • 先选出最小的质数2。用2去除掉所有2的倍数（4、6、8、10、12、14、16、18、20、22、24、26、28）。我们把这些数字标记成非质数（或删除）。

   剩下的数字：

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29
   

3. 接下来是下一个未被标记的数字：

   • 下一个未被标记的数字是3。用3去除掉所有3的倍数（9、15、21、27）。我们也把这些标记成非质数（或删除）。

   剩下的数字：

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29
   

4. 继续这个过程：

   • 继续用下一个未被标记的数字去除它的倍数。下一个数字是5，它的倍数（25）在这个范围内也被标记为非质数。

   最终的质数：

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29
   

5. 结束筛选：

   • 一旦我们处理完所有的小质数（不超过最大数的平方根），剩下的未被标记的数字就是质数。

总结：

埃拉托斯特尼筛法是一个聪明的数学工具，帮助我们快速找到一串数字中的所有质数。通过逐步筛选掉不是质数的数字，我们可以很容易地找出质数。这种方法就像一个超级有效的筛子，把所有非质数筛掉，只留下纯净的质数。

此方法的终止条件

在埃拉托斯特尼筛法中，筛选过程的终止条件是当当前筛选的质数 ( p ) 的平方大于给定范围的最大值时。具体来说，当我们处理到一个质数 ( p ) 时，只需要将其倍数（从 ( p^2 ) 开始）筛除即可。筛选的终止条件可以总结如下：

终止条件

1. 平方根终止：
   当质数 ( p ) 的平方 ( p^2 ) 超过我们需要筛选的最大数字（上限）时，筛选可以终止。也就是说，当 ( p^2 ) 大于给定范围的最大值 ( N ) 时，后续的倍数筛选已经不必要了，因为所有更大的倍数也会被更小的质数筛选过。

2. 处理完所有质数：
   在筛选过程中，我们会按照从小到大的质数逐一进行筛选。当我们处理到当前范围内的最大质数时，如果这个质数的平方还没有超出最大范围，那么继续筛选它的倍数，否则筛选结束。

为什么这样终止？

• 因为较大的质数的倍数：
  如果我们在处理较大的质数，它们的倍数会超过范围的最大值 ( N )。所以，一旦质数的平方 ( p^2 ) 大于 ( N )，剩下的质数的倍数已经不会影响到范围内的其他数字。

举个例子

假设我们要找出小于50的所有质数：

1. 开始筛选：

   • 2：筛除2的倍数（4, 6, 8, 10, …）
   • 3：筛除3的倍数（9, 12, 15, 18, …）
   • 5：筛除5的倍数（25, 30, 35, 40, …）

2. 判断平方：

   • 质数2的平方是4，4 < 50，继续筛选。
   • 质数3的平方是9，9 < 50，继续筛选。
   • 质数5的平方是25，25 < 50，继续筛选。
   • 质数7的平方是49，49 < 50，继续筛选。
   • 质数11的平方是121，121 > 50，停止筛选。

在这里，筛选过程停止，因为11的平方超过了50。

总结：

埃拉托斯特尼筛法的终止条件是当当前质数的平方超过了需要筛选的最大范围时。这个方法通过确保只处理必要的质数筛选步骤，来有效地找到所有质数。

优化空间

埃拉托斯特尼筛法已经很有效了，但我们可以通过一些小技巧让它更快、更节省空间。这里是几个可以优化的地方：

1. 只检查质数的倍数

为什么优化？

• 原来的方法是从 p * p 开始标记倍数，这样可以减少不必要的计算。我们只需要考虑从 p 的平方开始的倍数，因为更小的倍数已经被之前的质数处理过了。

优化点：

• 当 p 是一个质数时，所有小于 p 的倍数已经被筛选掉，所以我们从 p * p 开始标记。

举个例子：

• 假如我们已经找到质数2，那么2的倍数（4, 6, 8, 10, …）已经被处理了。当我们检查质数3时，3的倍数（9, 12, 15, …）从 p * p（即9）开始标记，因为小于9的倍数已经被2处理过了。

2. 只处理奇数

为什么优化？

• 偶数除了2之外，都是非质数。所以，我们可以跳过所有偶数，减少计算量。

优化点：

• 我们可以只考虑奇数的质数。这样，数组中只需要保存奇数的位置，节省空间和时间。

举个例子：

• 如果我们只考虑奇数2（忽略偶数3），我们的范围从2开始到最大数，我们只处理奇数的倍数。

3. 在标记非质数时跳过已处理的倍数

为什么优化？

• 有些倍数已经被其他质数处理过了，所以我们可以跳过这些重复的标记步骤。

优化点：

• 在标记非质数时，如果数字已经被标记为非质数，我们就不用再重复标记了。

举个例子：

• 如果数字9已经被标记过了，那么在处理下一个质数时，我们不再重复标记9。

总结

埃拉托斯特尼筛法可以通过以下几个方式进行优化：

1. 从质数 p 的平方开始标记倍数，这样避免了重复计算。
2. 只处理奇数质数，跳过偶数，节省时间和空间。
3. 跳过已经标记的倍数，避免重复工作。

这些优化方法使得筛选过程更加高效，让我们可以更快找到质数。

欧式筛法

通过上述的优化，我们就可以得到欧式筛法

1. 从质数 p 的平方开始标记倍数，这样避免了重复计算。
2. 只处理奇数质数，跳过偶数，节省时间和空间。
3. 跳过已经标记的倍数，避免重复工作。

总结

质数筛是一种用来找出一系列数字中所有质数的有效方法。它通过系统地筛除所有非质数，只留下质数。最基本的质数筛法是埃拉托斯特尼筛法，它从最小的质数开始，逐步筛除倍数，直到我们找出所有质数。为了提高效率，欧式筛法对经典筛法进行了优化，包括从质数的平方开始筛选、只处理奇数和避免重复标记等。这些优化使得筛选过程更加快速和节省空间。

质数筛不仅在数学中有重要的应用，也在计算机科学、密码学等领域中发挥着关键作用。通过掌握质数筛法，我们能够更好地理解质数的性质，并在解决实际问题时提高计算效率。