由于普通的筛法求素数的时候出现了一个数被多次标记的情况,所以效率比较低,我们可以使用线性筛来标记。线性筛中,每个数只被标记一次,时间复杂度为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;
        }
    }
}

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

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注