当前位置：首页 > news >正文

从数学到代码：一文详解埃拉托色尼筛法（埃式筛）

news 2025/6/13 9:27:28

文章目录

一、什么是埃式筛？
二、埃式筛的原理：层层筛选，留下质数
三、代码实现：将数学思想转化为编程语言
四、性能分析：埃式筛的优势与局限
五、埃式筛的应用场景

在算法的浩瀚星空中，质数筛选算法如同璀璨的星辰，而埃拉托色尼筛法（Sieve of Eratosthenes，简称埃式筛）则是其中最为耀眼的一颗。它以简洁优雅的思想和高效的实现，成为计算机科学与数学领域筛选质数的经典算法。无论是编程新手，还是经验丰富的开发者，都能从埃式筛中领略到算法与数学结合的精妙之处。接下来，我们就一同走进埃式筛的世界。

一、什么是埃式筛？

埃式筛是古希腊数学家埃拉托色尼在公元前三世纪提出的一种快速找出一定范围内所有质数的算法。质数，又称素数，是指在大于 1 的自然数中，除了 1 和它自身外，不能被其他自然数整除的数。例如 2、3、5、7、11 等都是质数，而 4（能被 2 整除）、6（能被 2 和 3 整除）等则不是。埃式筛的核心目标，就是通过一套巧妙的筛选机制，高效地找出给定区间内的所有质数。

二、埃式筛的原理：层层筛选，留下质数

埃式筛的原理基于一个简单而深刻的数学事实：任何一个合数（非质数）都可以表示为若干个质数的乘积。算法从最小的质数 2 开始，将 2 的所有倍数（除了 2 本身）标记为非质数；接着找到下一个未被标记的数 3，将 3 的所有倍数（除了 3 本身）标记为非质数；以此类推，直到遍历完所有小于等于目标范围平方根的数。那些最终未被标记的数，就是我们要找的质数。

举个例子，假设我们要找出 1 到 100 之间的所有质数。首先，我们将 2 的倍数 4、6、8、10…98、100 标记为非质数；然后处理 3，将 3 的倍数 6（已标记）、9、12、15…96、99 标记为非质数；接着是 5，将 5 的倍数 10（已标记）、15（已标记）、20、25…95、100 标记为非质数；再处理 7，将 7 的倍数 14、21、28…91、98 标记为非质数。经过这样一轮筛选，1 到 100 之间未被标记的数 2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97 就是我们要找的质数。

为什么只需要遍历到目标范围的平方根呢？这是因为如果一个数 n 是合数，那么它一定有一个小于等于 $\sqrt{n}$ 的质因数。例如，对于 36，它的平方根约为 6，而它的质因数 2、3 都小于等于 6。所以，只要我们遍历到 $\sqrt{n}$ ，就可以把 n 以内的所有合数都标记出来，从而找出所有质数。

三、代码实现：将数学思想转化为编程语言

下面，我们用 C++ 语言来实现埃式筛算法：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;vector<int> sieveOfEratosthenes(int n) {// 边界条件处理：如果 n 小于 2，直接返回空数组if (n < 2) return {};// 创建一个布尔数组，初始假设所有数都是质数vector<bool> isPrime(n + 1, true);isPrime[0] = isPrime[1] = false; // 0 和 1 不是质数// 只需要检查到 sqrt(n)即可int sqrtN = sqrt(n);for (int i = 2; i <= sqrtN; ++i) {if (isPrime[i]) {// 将 i 的所有倍数标记为非质数// 从 i*i 开始，因为小于 i*i 的 i 的倍数已经被标记过了for (int j = i * i; j <= n; j += i) {isPrime[j] = false;}}}// 收集所有质数vector<int> primes;for (int i = 2; i <= n; ++i) {if (isPrime[i]) {primes.push_back(i);}}return primes;
}int main() {int n = 100;vector<int> primes = sieveOfEratosthenes(n);cout << "小于等于" << n << "的质数有：" << endl;for (int prime : primes) {cout << prime << " ";}cout << endl;return 0;
}

在上述代码中，我们首先创建一个布尔类型的vector容器isPrime ，用于标记每个数是否为质数，初始时假设所有数都是质数（标记为true）。然后通过两层循环，外层循环从 2 遍历到目标范围的平方根，内层循环用于标记当前质数的所有倍数为非质数。最后，遍历数组，将未被标记为非质数的数收集起来，即为我们要找的质数。

四、性能分析：埃式筛的优势与局限

埃式筛的时间复杂度为 O(n log log n) ，相比于暴力枚举法（时间复杂度为 O(n $\sqrt{n}$ )，埃式筛在处理较大范围的质数筛选时效率有了显著提升。这是因为埃式筛通过一次遍历，同时标记多个合数，减少了不必要的判断。

然而，埃式筛也并非完美无缺。它的空间复杂度为 O(n) ，需要额外的数组来存储每个数是否为质数的标记信息。当处理极大范围内的质数筛选时，可能会面临内存不足的问题。此外，在某些特定场景下，如只需要判断一个数是否为质数，而不是筛选一定范围内的所有质数，埃式筛可能就不如其他专门的质数判定算法（如米勒 - 拉宾测试）高效。