两边同时取对数，\(\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)}}3. 狄利克雷卷积狄利克雷（Dirichlet）卷积是数论函数的基本运算，其重要程度相当于代数中的四则运算 。3.1 定义与性质为数列定义卷积，自然想到加法卷积 \(c_k = \sum\limits_{i + j = k} a_ib_j\) ， 但加法卷积不能保留积性 。让我们发散想象力，如果将加法换成乘法，结果如何？这引出了 狄利克雷卷积：
\[h(n) = \sum\limits_{d\mid x} f(d) g\left(\dfrac n d\right)\]上式简记为 \(h = f * g\) 。按照定义式计算狄利克雷卷积，复杂度为调和级数的 \(\mathcal{O}(n\ln n)\) 。
接下来证明一些狄利克雷卷积的性质 。
性质 1：狄利克雷卷积具有 交换律 ， 结合律，分配律 。交换律：
\[\begin{aligned}(f * g)(n) & = \sum\limits_{d\mid n} f(d) g\left(\dfrac n d\right) \\& = \sum\limits_{d'\mid n} f\left(\dfrac n {d'}\right) g\left(d'\right) \\& = \sum\limits_{d'\mid n} g(d')f\left(\dfrac n {d'}\right) \\& = (g * f)(n)\end{aligned}\]其中 \(d' = \dfrac n d\) 。因此 \(f * g = g * f\) 。
结合律：
\[\begin{aligned}((f * g) * h)(n) & = \sum\limits_{d\mid n} \left(\sum\limits_{i\mid d} f(i) g\left(\dfrac d i\right)\right) h\left(\dfrac n d\right) \\& = \sum\limits_{i\mid n} f(i) \left(\sum\limits_{d = ki \land d\mid n} g\left(\dfrac d i\right) h\left(\dfrac n d\right)\right) \\& = \sum\limits_{i\mid n} f(i) \left(\sum\limits_{k \mid \frac n i} g\left(k\right) h\left(\dfrac {\frac n i} k\right)\right) \\& = (f * (g * h))(n)\end{aligned}\]其中 \(k = \dfrac d i\) 。因此 \((f * g) * h = f * (g * h)\) 。
分配律：
\[\begin{aligned}((f + g) * h)(n) & = \sum\limits_{d\mid n} (f(d) + g(d)) h\left(\dfrac n d\right) \\& = \sum\limits_{d\mid n} f(d)h\left(\dfrac n d\right) + \sum\limits_{d\mid n} g(d)h\left(\dfrac n d\right) \\& = (f * h + g * h)(n)\end{aligned}\]因此 \((f + g) * h = f * h + g * h\) 。证毕 。
性质 2：\(\epsilon * f = f\) 。推荐阅读
- 前端程序员学习 Golang gin 框架实战笔记之一开始玩 gin
- 1 Libgdx游戏学习——环境配置及demo运行
- 苹果ipad分屏功能怎么使用（ipad 9可以分屏学习吗)
- Go设计模式学习准备——下载bilibili合集视频
- 学习ASP.NET Core Blazor编程系列五——列表页面
- 七 Netty 学习：NioEventLoop 对应线程的创建和启动源码说明
- ZCTF note3：一种新解法
- 学习ASP.NET Core Blazor编程系列四——迁移
- 五 Netty 学习：服务端启动核心流程源码说明
- 【前端必会】走进webpack生命周期，另类的学习方法
