欧拉筛（又称线性筛）_ola筛

清楚明白的博客！

其中ola筛就是少了很多重复，必须理解 if(n % primes[j])break; 是因为什么！（数学逻辑推理证明了能够减少多次重复筛选）

例题：

https://ac.nowcoder.com/acm/contest/21753/J

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7+10;
int st[N];
int primes[N], cnt;
void ola()
{
    st[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= N; j++)
        {
            st[primes[j] * i] = 1;
            if (i % primes[j] == 0)
                break;
        }
    }
}
int a[N];
int main()
{
    ola();
    int n;
    scanf("%d", &n);
    int ans = 0;
    int x;
    while (n--)
    {
        scanf("%d", &x);
        if (!st[x])
        {
            a[ans++] = x;
        }
    }
    printf("%d\n", ans);
    if (!ans)
    {
        printf("-1");
        return 0;
    }
    sort(a, a + ans);
    for (int i = 0; i < ans; i++)
    {
        printf("%d ", a[i]);
    }
}

几个需要注意的坑点：

1、st初始化似乎不能在外面？（int st[N]={1,1}会提示你编译错误）

2、N赋值的时候必须+10或+5，否则会出现很傻的边界debug问题

3、对于卡的时间紧的题目，必须scanf和printf！（这道题如果不用这两个就TLE了）