埃拉托斯特尼筛法

· · 算法·理论

一、埃拉托斯特尼筛法的定义

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种古老的质数筛查算法，由古希腊数学家埃拉托斯特尼所提出，用于检定素数。其基本思想是：如果一个数是质数，那么它的倍数肯定不是质数，利用事先定义的线性表以打表方式标记非质数，则剩下的数就是素数。

二、埃拉托斯特尼筛法的步骤

初始准备

先列出从2开始的序列（假设要筛选出一定范围内的素数，这个范围的起始数为2）。例如要筛选2到25之间的素数，列出2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25这样的序列。

标记第一个素数并划去其倍数

标出序列中的第一个素数（2是第一个素数），然后将剩下序列中从第二项开始每隔一项划掉（即2的倍数）。

循环操作

查看剩下的序列，如果现在这个序列中最大数小于第一个素数的平方，那么剩下的序列中所有的数都是素数；否则返回第二步。例如在上述序列中，25大于2的平方，所以要继续操作。此时剩下序列中的第一个素数是3，再将主序列中3的倍数划出。由于25仍然大于3的平方，所以还要返回第二步。现在序列中第一个素数是5，将序列中5的倍数划出。如此循环进行，最后去掉被划掉（标记为非素数）的数字，剩下的就是素数。例如在2到25之间，剩下的素数是2、3、5、7、11、13、17、19、23。

三、埃拉托斯特尼筛法的优缺点

优点

简单直观： 算法逻辑容易理解，实现起来比较直接，适合初学者学习素数筛选算法。例如在教学过程中，通过简单的数列标记就可以让学生理解素数筛选的基本概念。

对于较小范围效率较高：在确定较小范围内的质数时，该算法能够较快地得出结果。比如在计算100以内的素数时，可以迅速完成筛选。

缺点

计算效率低下（针对大范围内）：其时间复杂度为 O(n\;\log\;\log\;n) ，当要确定大范围内的质数时，随着范围的增大，计算量会显著增加。例如在寻找较大数值范围内的素数，如1000000以上的素数时，该算法的计算速度会变得很慢。

四、埃拉托斯特尼筛法的应用示例

C语言实现示例

在C语言中，可以使用数组来实现埃拉托斯特尼筛法。例如，可以定义一个数组来表示从1到n的数，先将数组元素都初始化为表示是素数的状态，然后按照埃拉托斯特尼筛法的步骤，将素数的倍数对应的数组元素标记为非素数状态，最后剩下的为素数状态的元素对应的数就是素数。下面是一个简单的代码框架：

#include <stdio.h> 
#include <stdlib.h> 

// 埃拉托斯特尼筛法函数 
void sieve(int n) { 
    int *prime = (int *) malloc((n + 1) * sizeof(int)); 
    for (int i = 2; i <= n; i++) { 
        prime[i] = 1; 
    } 

    for (int p = 2; p * p <= n; p++) { 
        if (prime[p] == 1) { 
            for (int i = p * p; i <= n; i += p) { 
                prime[i] = 0; 
            } 
        } 
    } 

    // 输出素数 
    for (int i = 2; i <= n; i++) { 
        if (prime[i] == 1) { 
            printf("%d ", i); 
        } 
    } 

    free(prime); 
} 

int main() { 
    int n = 100; 
    sieve(n); 
    return 0; 
}

Python实现示例

在Python中，可以利用列表来实现类似的功能。例如创建一个布尔类型的列表，初始时假设所有数都是素数（对应列表元素为 True ），然后按照埃拉托斯特尼筛法的步骤将合数对应的列表元素标记为 False ，最后列表中为 True 的元素对应的数就是素数。以下是示例代码：

def sieve(n): 
    is_prime = [True] * (n + 1) 
    is_prime[0] = is_prime[1] = False 

    p = 2 
    while p * p <= n: 
        if is_prime[p]: 
            i = p * p 
            while i <= n: 
                is_prime[i] = False 
                i += p 
        p += 1 

    primes = [] 
    for i in range(2, n + 1): 
        if is_prime[i]: 
            primes.append(i)  
    return primes 

result = sieve(100) 
print(result)

五、埃拉托斯特尼筛法的改进

乌拉姆螺旋改进

乌拉姆螺旋的优点是可以避免重复计算。它通过一种特殊的螺旋排列方式对数字进行处理，结合埃拉托斯特尼筛法的思想来提高计算效率，不过其实现方式相对复杂一些。

狄克逊素数筛法改进

狄克逊素数筛法的原理是使用多个基数。它采用分块素筛等步骤，通过多个基数的运用来改进埃拉托斯特尼筛法在筛选素数时的效率问题。

埃拉托斯特尼筛法+哥伦布筛法（变种）

这种变种也是为了提高素数筛选的效率，结合了哥伦布筛法的一些特性与埃拉托斯特尼筛法的基本原理，在处理大数值范围的素数筛选时可能会有更好的性能表现。