筛法
当我们需要获取一个区间内的所有素数的时候，我们肯定会想到筛法。
比较常见的是埃氏筛和线性筛。
他们的实现难度不高，但核心思想有所不同。
埃氏筛
考虑一个 $p \in \mathbb{P}$ 和任意一个一个大于 $2$ 的正整数 $x$，$\forall y = xp, y \notin \mathbb{P}$。
这就是埃氏筛的核心。筛去每个素数的所有倍数。
线性筛与数论函数
发布时间 2023-10-12 21:41:48作者: Arknights_Aak
当我们需要获取一个区间内的所有素数的时候，我们肯定会想到筛法。
比较常见的是埃氏筛和线性筛。
他们的实现难度不高，但核心思想有所不同。
考虑一个 $p \in \mathbb{P}$ 和任意一个一个大于 $2$ 的正整数 $x$，$\forall y = xp, y \notin \mathbb{P}$。
这就是埃氏筛的核心。筛去每个素数的所有倍数。