【算法】素数筛

引子

本文探讨寻找从2到n所有质数的几种方法，并在复杂度上进行比较。

1. 常规的寻找质数法

思想：对于每一个数字，从2开始枚举到该数字的算术平方根处，若存在某个枚举到的数能整除当前数字，则该数字非质数。

C语言代码段如下：

int isPrime;

for(int i = 2; i <= n; i++) {
    isPrime = 1;
    for(int j = 2; j*j <= i; j++) {
        if(i % j == 0) {
            isPrime = 0;
            break;
        }
    }
    if(isPrime) printf("%d\n", i);
}

该寻找方法，复杂度为$O(n\sqrt{n})$。

2. 埃拉托斯特尼筛法

思想：

1. 维护一个表，表项为0代表该表项下标是质数。
2. 已知2是最小的质数，在表中将所有以2的倍数为下标的表项标注为1，寻找表项为0的最小下标，该下标为一个质数。
3. 标记以该质数倍数为下标的表项，接着寻找表项为0的最小下标，该下标同样也是一个质数。
4. 回到第二步，做类似操作。

C语言代码段如下：

int prime[n] = {0};
for(int i = 2; i <= n; i++) {
    if(!prime[i]) {
        printf("%d\n", i);
        for(int j = i*i; j <= n; j+=i) { //初始化j为i*i, 因为其为未被筛过的，且以i为因子的合数
            prime[j] = 1;
        }
    }
}

该寻找方法，复杂度为$O(nloglogn)$。根据素数定理，可以通过积分算出这个复杂度，详情参考这里。

该方法存在问题，比如在遍历到2、3时，下标为12的表项，都会经历一次赋值操作。

3. 欧拉筛法

思想：

1. 维护一个记录表，表项为0代表该表项下标是质数。维护一个质数表，装质数本身。
2. 已知2是最小的质数，放入质数表。
3. 从2开始，每个数都与质数表里的数相乘，将记录表对应下标表项修改为1。
4. 若遍历到某个数，能被质数表中某一质数整除，则回到第二步，做类似操作。

C语言程序如下：

#include <stdio.h>

int main(int argc, char **argv) {
    int isNotPrime[1000] = {0};
    isNotPrime[0] = 1;
    int primeList[1000] = {0};
    int count = 0;
    int n = 100;
    for(int i = 2; i <= n; i++) {
        if(isNotPrime[i] == 0) {
            printf("%d\n", i);
            primeList[count++] = i;
        }

        for(int j = 0; j < count && i*primeList[j] <= n; j++) {
            isNotPrime[primeList[j]*i] = 1;
            if(i % primeList[j] == 0) break;
        }
    }
    return 0;
}

该寻找方法，复杂度为$O(n)$。