素数筛和线性筛

问题描述：

快速的求出一个数 n 是不是素数。

素数筛

素数筛的原理就是利用已知的素数来标记合数，然后将素数进行排序。
上例子：n = 4

第一个素数是2， 第一次我们先把2的倍数都给标记了，一直到 n 位置
然后把 2 放到数组中的prime[1] 中去， prime[0]记录已经找到素数的数量，prime[0]加一。

接下来进行对3的标记。

当查到4的时候，他是2的倍数，是合数被标记过，我们跳过去判断5

我们可以到prime[0]等于n的时候停止，也可以直接找出很多个，prime[n]的结果就是第n个素数。这里prime[4]=7，正确。

代码

#include <stdio.h>
#include <string.h>
#define max_n 200000

int prime[max_n + 5] = 0;

int main() {
    for (int i = 2; i <= max_n; i++) {
        if (!prime[i]) {
            prime[++prime[0]] = i; // prime[0]记录素数的数量，然后将素数按顺序放置
            for (int j = 2; j * i <= max_n; j++) {
                prime[j * i] = 1; //标记合数
            }
        }
    }
    printf("%d\n", prime[10001]);
    return 0;
}

线性筛

素数筛会重复标记两个素数的公倍数，他利用已经发现的素数依次进行标记，减少了标记的次数。
第一步用2进行标记，prime[0]++,知道标记到 他的平方 4为止。

第二次找到素数3的时候，prime[0]++,然后我们从第一个素数开始，每一个素数和3相乘，将所得到的合数进行标记，知道3的平方9为止。

第三次是4，已经被标记过，这里直接跳过。

源码

#include <stdio.h>
#define max_n 200000

int prime[max_n + 5] = {0};

int main() {
    for (int i = 2; i <= max_n; i++) {
        if (!prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0]; j++) {
            if (i * prime[j] > max_n) break;
            prime[i * prime[j]] = 1; // 对合数进行标记
            if (i % prime[j] == 0) break; //到 n * n为止，因为后面的可以用两个用新找出来的素数进行标记
        }
    }
    printf("%d\n", prime[10001]);
    return 0;
}