线性筛素数（欧拉筛）

线性筛法，也称为欧拉筛法，是一种高效的素数筛选算法，它可以在O(n)的时间复杂度内筛选出小于等于n的所有素数。下面是线性筛素数的基本原理和代码示例：

基本原理：

1. 初始化一个布尔数组 `is_prime`，将所有的元素初始化为 `true`，表示所有数都是素数。

2. 从2开始遍历到n，如果当前数字 i 是素数（即 `is_prime[i]` 为 `true`），则将其加入素数数组。

3. 然后遍历素数数组中的每个素数 `primes[j]`，将 `i * primes[j]` 标记为非素数（合数），即将 `is_prime[i * primes[j]]` 设为 `false`。同时，如果 `i` 能整除 `primes[j]`，则停止遍历，因为后续的 `i * primes[j]` 已经被其他素数筛选过。

4. 重复上述步骤，直到遍历完成，得到小于等于 n 的所有素数。

这个算法的核心思想是通过遍历每个数，将合数逐一筛掉，最终得到素数数组。这是一种高效的素数筛选方法，时间复杂度为 O(n)。

int primes[N],cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
 
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}