线性筛素数详解

一、简介

线性筛素数，顾名思义，是一种用线性时间复杂度求出所有素数的方法。相比于其他素数筛法，线性筛素数更加高效，因此在实际应用中经常被使用。

二、原理

线性筛素数的核心思想是将每个数都标记为“素数”或“合数”，并在记录同时筛选掉它的所有倍数，这使其无需对每个数都判断是否是素数。

三、实现

首先，需要创建一个长度为n+1的数组isPrime，用来标记每个数是否为素数

bool isPrime[MAX_N + 1];  // MAX_N为所求最大值

一开始，将isPrime数组置为true，表示假设所有数都为素数。

for (int i = 2; i <= MAX_N; i++) {
    if (isPrime[i]) {  // 若i为素数
        prime[++cnt] = i;  // 将其加入素数数组中
    }

    for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
        isPrime[i * prime[j]] = false;  // 筛去合数
        if (i % prime[j] == 0) {  // 优化2
            break;
        }
    }
}

其中，主循环枚举i从2到n，若i为素数，则将它加入素数数组中，并遍历它的所有倍数j，将它们标记为合数。在遍历的过程中，若发现当前数i是某个素数的倍数，那么就停止遍历i的倍数，因为它已经被筛选掉了。

四、优化

在实际应用中，线性筛素数还有一些优化操作，可以进一步提高效率。

1、使用已有的素数数组

仔细观察上述代码可以发现，每次筛选合数时都要遍历已经求得的素数数组。这乍一看，效率还不如普通的试除法，但是其时间复杂度是线性的，实际效率也很高。但是，我们可以想到一个优化，那就是直接使用已经求得的素数来筛选。

for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
    isPrime[i * prime[j]] = false;
    if (i % prime[j] == 0) {
        break;
    }
}

通过使用已有的素数数组，在筛选的过程中，不仅效率提高了，同时也减少了计算量。

2、拆分判断

接着，我们可以注意到，在上述代码中，除数同为质数时，同样的操作被执行了多次。比如，当i是2的倍数时，就需要将2从它的所有倍数中筛掉；当i是3的倍数时，需要将3从它的所有倍数中筛掉。在这种情况下，代码中会重复调用，算法效率会受到影响。那么是否可以做一些调整，提高执行效率呢？答案是肯定的，在这里我们可以把这些操作拆分开来，以减少重复操作。

for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
    isPrime[i * prime[j]] = false;
    if (i % prime[j] == 0) {
        break;
    }
}

3、减少判断次数

最后，我们需要注意到，当我们在判断某个数是否为素数时，实际上只需要判断它是否是当前素数数组中所有素数的倍数就可以了。显然，这个数可不是所有数的倍数，因此，以它为起点递增的倍数也不可能是所有数的倍数，只有递增素数的倍数能够被筛掉。基于此，我们可以减少判断次数。

for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
    isPrime[i * prime[j]] = false;
    if (i % prime[j] == 0) {
        break;
    }
}

五、总结

线性筛素数是一种高效的素数判定方法，通过将每个数都标记为“素数”或“合数”，并在记录同时筛选掉它的所有倍数，实现了无需对每个数都判断是否是素数。在实际应用中，可以通过使用已有的素数数组、拆分判断和减少判断次数等方式，进一步提高算法效率。

六、完整代码

const int MAX_N = 1000000;

bool isPrime[MAX_N + 1];
int prime[MAX_N + 1];
int cnt = 0;

void linearSieve() {
    for (int i = 2; i <= MAX_N; i++) {
        if (isPrime[i]) {
            prime[++cnt] = i;
        }

        for (int j = 1; j <= cnt && i * prime[j] <= MAX_N; j++) {
            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    memset(isPrime, true, sizeof(isPrime));
    linearSieve();

    for (int i = 1; i <= cnt; i++) {
        printf("%d\n", prime[i]);
    }

    return 0;
}