素筛法之埃拉托斯特尼筛法

素数的判断以及筛选方式不只有一种。而这些方法里面也有快有慢。有可能用时间复杂度较高的方法会导致计算超出时间限制或者一个项目运行效率不高。今天分享一篇埃拉托斯特尼素筛法的算法。

朴素逻辑

1. 拿出一张纸，写上 2 到 N的所有数字

2. 找到第一个没被划掉的数字（也就是 2），它肯定是素数

3. 把 2 的倍数（4, 6, 8, 10...）全部划掉（标记为合数）

4. 找到下一个没被划掉的数字（3），它是素数

5. 把 3 的倍数（6, 9, 12, 15...）全部划掉

6. 找到下一个（5），划掉 5 的倍数...

7. 一直重复

算法逻辑

1. 创建一个布尔数组，初始将所有2到N的数标记为素数

2. 从最小的素数2开始，筛除它的所有倍数（这些倍数必然是合数）

3. 找到下一个未被筛除的数，它就是下一个素数，重复步骤2

4. 只需遍历到√N即可，因为大于√N的合数必然有小于√N的质因数

5. 内层循环从p p开始，因为小于p p的倍数已经被更小的素数筛除过了

C语言代码

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

void sieveOfEratosthenes(int N) {
    // 创建布尔数组，初始全部标记为true（假设所有数都是素数）
    bool isPrime[N + 1];
    for (int i = 2; i <= N; i++) {
        isPrime[i] = true;
    }

    // 从2开始筛除非素数
    for (int p = 2; p * p <= N; p++) {
        // 如果p是素数，则筛除它的所有倍数
        if (isPrime[p] == true) {
            for (int i = p * p; i <= N; i += p) {
                isPrime[i] = false;
            }
        }
    }

    // 输出所有素数
    printf("2到%d之间的素数有：\n", N);
    for (int i = 2; i <= N; i++) {
        if (isPrime[i] == true) {
            printf("%d ", i);
        }
    }
    printf("\n");
}

int main() {
    int N;
    printf("请输入一个整数N（N >= 2）：");
    scanf("%d", &N);

    if (N < 2) {
        printf("N必须大于等于2！\n");
        return 1;
    }

    sieveOfEratosthenes(N);

    return 0;
}

核心优势要点

1. 内层循环从p²开始，避免重复筛除，确保每个合数只被其最小质因数筛除一次

2. 外层循环只需到√N，减少不必要的遍历

3. 使用布尔数组标记，空间换时间，时间复杂度接近O(N log log N)

其实它也有缺点

此方法相较于暴力筛选法肯定快了很多，但是也有不足之处，那就是其实也会重复标记，如考虑2和3的倍数时，6，12，18等合数会被标记两次0。接下来介绍的方法会规避此点。