【数论】素数（二）：素数筛法（埃式筛、欧拉筛、区间筛）

default111

已于 2022-03-05 19:57:46 修改

阅读量547

点赞数 1

分类专栏：算法竞赛文章标签：算法数学 c++

于 2022-03-05 19:45:58 首次发布

本文链接：https://blog.csdn.net/default012/article/details/123299861

版权

我的数论-素数部分博客共5part：
基本概念、性质、猜想、定理
 素数筛法（埃式筛、欧拉筛、区间筛）
素数判断法（朴素法、模6法、Rabin-Miller及改进）
数的分解（Pollard-rho）
梅森素数（Lucas_Lehmer判定法）

文章目录

素数筛法

素数筛法

埃式筛法

$O (n l o g l o g n)$

bool b[N];
bool prime[N];
void solve(int x)
{
   
    for (int i = 0; i <= x; i++)
        prime[i] = true;
    b[0] = b[1] = 0;
    for (int i = 2; i <= x; i++)
        if (b[i])
            for (int j = i << 1; j <= x; j += i)
                prime[j] = false;
}