筛法

在实数范围内，每个合数都可以被表示为多个质数的乘积根据这个定理，我们可以写出高效筛选出一个范围内所有质数的算法。

1. 朴素筛：

思想：

设置两个数组：judge数组用来标记素数，我们在不断筛选的过程中，如果这个数被标记上了，那它就不是素数。prime数组用来存储具体的素数。

从2开始遍历，如果i没有被标记过，说明它是素数，将其加入结果prime数组中，接着利用内部for循环遍历标记i的倍数。

这种情况下，后面的数会被重复标记，比如说12，在对2进行筛选的时候，2*6（12）会被标记，接着对3进行筛选的时候，3*4（12）会再次被标记，即合数的倍数也会被标记，这显然是不需要的。这种情况会出现非常多的次数，所以朴素筛算法性能不好。

// 朴素筛模板 
bool judge[maxn];
int prime[maxn], cnt = 0;
int getPrimes(int n){
    for(int i = 2; i <= n; i++){
        if(!judge[i])
            prime[cnt++] = i;
        // 这里为了时间性能，从i*i开始标记（因为前面的已经被标记过了），将i的整数倍全部标记一遍
        for(int j = i * i; j <= n; j += i){
            judge[j] = true;
        }
    }
    return cnt;
}

---

2.埃氏筛

思想：

埃氏筛是从朴素筛改进而来的，从上面对于朴素筛的讨论我们可以清楚对于合数我们没必要再考虑，因为在对前面的质数的质数进行标记的时候我们已经将合数进行标记过了。所以我们可以将内层for循环写入if语句中。

较之朴素筛，埃氏筛选的时间性能已经得到了很大的提升，不过，我们可以想到的是，即便埃氏筛排除了后面合数被讨论的可能，但对于每个合数可能被前面两个素数给标记到，同样会出现重复的情况，所以埃氏筛还有可以改进的空间。

// 埃氏筛模板 
bool judge[maxn];
int prime[maxn], cnt = 0;
int getPrimes(int n){
    for(int i = 2; i <= n; i++){
        if(!judge[i]){
            prime[cnt++] = i;
            for(int j = i * i; j <= n; j += i){
                judge[j] = true;
            }
        }
    }
    return cnt;
}

---

3.线性筛

思想：

欧氏筛需要解决的后面每个合数可能被前面两个或多个素数给标记到的问题，我们可以规定每个合数只可以被其最小的一个质因子标记，比如说数字22，其会被2标记，也会被11标记，我们限定的就是如果被2标记到了，那么11就不要再标记了。

线性筛法能保证合数只会被最小质因子标记，时间性能大大提高。

// 线性筛模板 
bool judge[maxn];
int prime[maxn], cnt = 0;
int getPrimes(int n){
    for(int i = 2; i <= n; i++){
        if(!judge[i])
            prime[cnt++] = i;
        // 枚举prime
        for(int j = 0; prime[j] * i <= n; j++){
            judge[prime[j] * i] = true;
            // 整除中断，如果i是合数，那么其一定会被其最小质因子整除，质数会被一直枚举到自身为止
            if(i % prime[j] == 0){
                break;
            }
        }
    }
    return cnt;
}