for(int i = 2; i < N; i++)if(!vis[i]) {pr[++cnt] = i;for(int j = 2 * i; j < N; j += i) vis[j] = 1;}常数优化：根据合数 \(i\) 的最小质因子 \(\leq \sqrt i\) ， 可以从 \(i ^ 2\) 开始标记 。
for(int i = 2; i < N; i++)if(!vis[i]) {pr[++cnt] = i;if(1ll * i * i < N) // 防止 i * i 溢出导致 REfor(int j = i * i; j < N; j += i) vis[j] = 1;}埃氏筛的精髓在于其复杂度证明：不超过 \(n\) 的质数的倒数之和为 \(\mathcal{O}(\ln \ln n)\) 级别 。
\[\sum\limits_{p\in \mathbb{P}, p\leq n} \dfrac 1 p = \mathcal{O}(\ln \ln n)\]这说明埃氏筛的复杂度为 \(\mathcal{O}(n\ln \ln n)\) 。
证明来自戴江齐学长：
因为每个数只会被其素因子筛到 ， 所以 \(\sum\limits_{p\in \mathbb{P}, p\leq n} \dfrac 1 p = \sum\limits_{i = 1} ^ n \omega(i)\) 。
根据 \(d(i)\) 的计算式 ， \(\sum\limits_{i = 1} ^ n 2 ^ {\omega(i)} \leq \sum\limits_{i = 1} ^ n d(i)= \mathcal{O}(n\ln n)\) 。
根据 \(2 ^ x\) 的凸性和琴生不等式得 \(\sum\limits_{i = 1} ^ n 2 ^ {\omega(i)} \geq n 2 ^ {\frac{\sum_{i = 1} ^ n \omega(i)} n}\) ， 所以 \(2 ^ {\frac{\sum_{i = 1} ^ n \omega(i)} n} \leq \mathcal{O}(\ln n)\) 。
两边同时取对数 ， \(\dfrac {\sum_{i = 1} ^ n \omega(i)} n \leq \mathcal{O}(\ln \ln n)\) ， 因此 \(\sum\limits_{i = 1} ^ n \omega(i)\leq \mathcal{O}(n\ln\ln n)\) 。证毕 。
2.2 线性筛素数线性筛也称欧拉筛 ， 它和埃氏筛的思想类似 。
埃氏筛的优秀之处在于仅用质数的倍数筛去合数 ， 但合数会被多个质因子筛到 。让每个合数仅被筛一次就能做到线性 。
考虑用每个合数的 最小质因子 筛去它：从 \(2\) 到 \(n\) 枚举所有数 \(i\) 。对于每个 \(i\) ， 令其最小质因子为 \(p\) ， 则对于不大于 \(p\) 的质数 \(q\) ， \(iq\) 的最小质因子为 \(q\) 。将所有 \(iq\) 标记为合数 ， 则每个合数 \(c\) 仅在 \(i = \dfrac c m\) 时以 \(im\) 的形式删去 ， 其中 \(m\) 是 \(c\) 的最小质因子 。
综上 ， 有如下步骤：
- 从小到大遍历当前筛出的所有素数 \(pr_j\) ， 将 \(i\times pr_j\) 标记为合数 。
- 若 \(pr_j\mid i\) ， 退出循环 。因为 \(pr_j\mid i\times pr_k(k > j)\) ， 所以 \(i\times pr_k\) 的最小质因子为 \(pr_j\) 不是 \(pr_k\) ， 再筛就重复了 。
#include <bits/stdc++.h>using namespace std;constexpr int N = 1e8 + 5;bool vis[N];int n, q, pr[N / 16], cnt;int main() {cin >> n;for(int i = 2; i <= n; i++) {if(!vis[i]) pr[++cnt] = i;for(int j = 1; j <= cnt && i * pr[j] <= n; j++) {vis[i * pr[j]] = 1;if(i % pr[j] == 0) break;}}cin >> q;while(q--) {int x;scanf("%d", &x);printf("%d\n", pr[x]);}return 0;}2.3 线性筛积性函数线性筛提供了在线性时间内筛出具有特殊性质的积性函数在 \(1\sim n\) 处所有取值的基本框架 。只要积性函数 \(f\) 可在 \(\mathcal{O}(1)\) 时间内计算任意质数幂处的取值 \(f(p ^ k)\) ， 就适用线性筛 。
- 注意 ， 这只是 \(f\) 可线性筛的 充分但不必要 条件 。存在更弱的条件使得 \(f\) 可线性筛但并不常见 ， 如 \(\mathcal{O}(k)\) 计算 \(f(p ^ k)\) ， 这将在第三章介绍 。
for(int i = 2; i < N; i++) {if(!vis[i]) pr[++pcnt] = i, f[i] = ..., low[i] = i; // 单独算 f(p)for(int j = 1; j <= pcnt && i * pr[j] < N; j++) {vis[i * pr[j]] = 1;if(i % pr[j] == 0) { // i 与 p 不互质low[i * pr[j]] = low[i] * pr[j];if(i == low[i]) f[i * pr[j]] = ...; // i = p ^ k ， 单独算 f(p ^ {k + 1})else f[i * pr[j]] = f[i / low[i]] * f[low[i * pr[j]]];break;}low[i * pr[j]] = pr[j];f[i * pr[j]] = f[i] * f[pr[j]]; // i 与 p 互质 ， f(ip) = f(i)f(p)}}
经验总结扩展阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 为什么有些人会孤立认真学习的人
- 苹果ipad分屏功能怎么使用（ipad 9可以分屏学习吗)
- 前端程序员学习 Golang gin 框架实战笔记之一开始玩 gin
- 1 Libgdx游戏学习——环境配置及demo运行
- Go设计模式学习准备——下载bilibili合集视频
- 学习ASP.NET Core Blazor编程系列五——列表页面
- 小学生的学习动机是什么
- 七 Netty 学习：NioEventLoop 对应线程的创建和启动源码说明
- ZCTF note3：一种新解法
- 关于环境学习生活类的名言急
