【板子】筛法求素数-线性筛

由于普通的筛法求素数的时候出现了一个数被多次标记的情况，所以效率比较低，我们可以使用线性筛来标记。线性筛中，每个数只被标记一次，时间复杂度为O(N)

核心代码是下面这样的：（我下面这串代码求的是2-20000之间的素数）

int num[MAXN];
int prime[4 * MAXN] = {0};
bool vis[4 * MAXN] = {false};

int prime_cnt = 0;
void Euler()
{
    for (int i = 2; i <= 20000; ++i)
    {
        if (!vis[i]) //质数
        {
            prime[prime_cnt++] = i;
        }
        for (int j = 0; j < prime_cnt && i * prime[j] <= 20000; ++j)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~