筛法
素数筛法
引入
如果我们想要知道小于等于
一个自然的想法是对于小于等于
埃拉托斯特尼筛法
过程
考虑这样一件事情:对于任意一个大于
如果我们从小到大考虑每个数,然后同时把当前这个数的所有(比自己大的)倍数记为合数,那么运行结束的时候没有被标记的数就是素数了。
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
以上为 Eratosthenes 筛法(埃拉托斯特尼筛法,简称埃氏筛法),时间复杂度是
证明
现在我们就来看看推导过程:
如果每一次对数组的操作花费 1 个单位时间,则时间复杂度为:
其中 if (prime[i])
进入 true 分支的次数;
根据 Mertens 第二定理,存在常数
所以 Eratosthenes 筛法 的时间复杂度为
根据
当然,上面的做法效率仍然不够高效,应用下面几种方法可以稍微提高算法的执行效率。
筛至平方根
显然,要找到直到
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
这种优化不会影响渐进时间复杂度,实际上重复以上证明,我们将得到
只筛奇数
因为除 2 以外的偶数都是合数,所以我们可以直接跳过它们,只用关心奇数就好。
首先,这样做能让我们内存需求减半;其次,所需的操作大约也减半。
减少内存的占用
我们注意到筛选时只需要 bool
类型的数组。bool
数组的一个元素一般占用
我们可以使用 位运算 的相关知识,将每个布尔值压到一个比特位中,这样我们仅需使用
值得一提的是,存在自动执行位级压缩的数据结构,如 C++ 中的 vector<bool>
和 bitset<>
。
另外,vector<bool>
和 bitset<>
对程序有常数优化,时间复杂度 bitset<>
或 vector<bool>
优化后,性能甚至超过时间复杂度
参见 bitset: 与埃氏筛结合。
分块筛选
由优化「筛至平方根」可知,不需要一直保留整个 is_prime[1...n]
数组。为了进行筛选,只保留到 prime[1...sqrt(n)]
。并将整个范围分成块,每个块分别进行筛选。这样,我们就不必同时在内存中保留多个块,而且 CPU 可以更好地处理缓存。
设
值得注意的是,我们在处理第一个数字时需要稍微修改一下策略:首先,应保留
以下实现使用块筛选来计算小于等于
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
分块筛法的渐进时间复杂度与埃氏筛法是一样的(除非块非常小),但是所需的内存将缩小为
块大小
线性筛法
埃氏筛法仍有优化空间,它会将一个合数重复多次标记。有没有什么办法省掉无意义的步骤呢?答案是肯定的。
如果能让每个合数都只被标记一次,那么时间复杂度就可以降到
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
上面的这种 线性筛法 也称为 Euler 筛法(欧拉筛法)。
Note
注意到筛法求素数的同时也得到了每个数的最小质因子。
筛法求欧拉函数
注意到在线性筛中,每一个合数都是被最小的质因子筛掉。比如设
观察线性筛的过程,我们还需要处理两个部分,下面对
如果
那如果
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
筛法求莫比乌斯函数
定义
根据莫比乌斯函数的定义,设
若
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
筛法求约数个数
用
约数个数定理
定理:若
证明:我们知道
实现
因为
在这里简单介绍一下线性筛实现原理。
- 当
为质数时, ,同时设 ,其中 为 的最小质因子。 - 当
为 的质因子时, 。 - 当
互质时, 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
筛法求约数和
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
一般的积性函数
假如一个 积性函数
设合数
假如
本节部分内容译自博文 Решето Эратосфена 与其英文翻译版 Sieve of Eratosthenes。其中俄文版版权协议为 Public Domain + Leave a Link;英文版版权协议为 CC-BY-SA 4.0。
本页面最近更新:2024/5/16 19:30:19,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:iamtwz, StudyingFather, HeRaNO, Mr-Python-in-China, shuzhouliu, TravorLZH, weilycoder, wood3, YOYO-UIAT, 1804040636, 383494, aofall, CCXXXI, CoelacanthusHex, countercurrent-time, cubeheadsun, Early0v0, Enter-tainer, frank-xjh, gongyisheng, Great-designer, greyqz, H-J-Granger, hqztrue, ImpleLee, inkydragon, Ir1d, LJFYC007, luojiny1, Lutra-Fs, Marcythm, MegaOwIer, Menci, mgt, NachtgeistW, opsiff, partychicken, Peanut-Tang, PerfectPan, Persdre, shawlleyw, StableAgOH, Steaunk, SukkaW, sunruisjtu2020, TianKong-y, Tiphereth-A, TrisolarisHD, untitledunrevised, WAAutoMaton, WineChord, Xeonacid, YanWQ-monad, zhouyuyang2002
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用