埃拉托斯特尼筛法

定义

埃拉托斯特尼筛法(Sieve of Eratosthenes)是枚举某一范围内所有素数的古典算法,相传由公元前三世纪的古希腊学者埃拉托斯特尼提出,是仍在广泛使用的最古老算法之一。

原理

建立 2 到 n 的标记数组,从 2 开始:每遇到一个未被划去的数 p,即为素数,随后把 p²、p²+p、p²+2p 等所有 p 的倍数划去;处理到 √n 即可。时间复杂度 O(n log log n),接近线性。

优化与变体

只存奇数可省一半空间;分段筛(segmented sieve)按块处理以适配缓存并支持大区间;欧拉筛(线性筛)保证每个合数只被其最小素因子划一次,达到严格 O(n),还能顺带求积性函数。

应用

数论问题预处理、密码学素数分布实验、竞赛编程中的批量素数判定,以及作为算法教学中"空间换时间"的典型示例。