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

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

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

代码语言：javascript复制

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;
        }
    }
}

效率

0 人点赞