埃拉托斯特尼筛法

算法

一种高效的算法,用于找出一定范围内的所有素数。通过标记素数的倍数来筛选出所有素数。

时间复杂度:最差 O(n log log n)
空间复杂度:O(n)

算法讲解

埃拉托斯特尼筛法

介绍

埃拉托斯特尼筛法(Sieve of Eratosthenes)是一种古老而高效的素数筛选算法,由古希腊数学家埃拉托斯特尼(Eratosthenes,约公元前276年至前194年)发明。该算法通过筛选的方式,能够找出给定范围内的所有素数。它的核心思想非常简单:从2开始,将每个素数的倍数标记为合数,最终未被标记的数即为素数。这种方法在查找较大范围内的素数时特别高效,是最常用的素数生成算法之一。

算法步骤

  1. 创建一个从2到n的连续整数列表
  2. 初始,令p=2,这是最小的素数
  3. 从p²开始,将p的所有倍数(p×p, p×(p+1), p×(p+2)...)标记为合数
  4. 找到列表中第一个大于p且未被标记的数,这个数是素数,将其作为新的p
  5. 如果p² > n(或找不到这样的数),算法结束;否则,重复步骤3
  6. 最终,列表中所有未被标记的数即为素数

算法详解

以查找小于30的素数为例,演示埃拉托斯特尼筛法的过程:

第1步:创建列表

创建一个列表 [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步:从p=2开始

  • 2是素数,将2的倍数(4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28)标记为合数

...