【算法入门-14】筛法只能求质数？

• 上课的课件

  • 筛法只能求质数.pdf

• 参考资料

  • OiWiki：筛法求质数，欧拉函数，约数个数，约数和
  • 线性筛求 约数个数 与 约数和
  • OiWiki：bitset 优化筛法
  • 区间筛法
  • B 站视频：欧拉筛

• 重点

  • 一个合数 $n$ 必然存在不超过 $\sqrt{n}$ 的质因子
  • 假设一个数分解质因数后为 $x = a_1^{b_1} \times a_2^{b_2} \times a_3^{b_3}$
  • 那么 $x$ 的约数个数为: $(b_1 + 1) \times (b_2 + 1) \times (b_3 + 1)$
  • 那么 $x$ 的约数和为: $(1 + a_1^1 + a_1^2 + \cdots + a_1^{b_1}) \times (1 + a_2^1 + a_2^2 + \cdots + a_2^{b_2} \times (1 + a_3^1 + a_3^2 + \cdots + a_3^{b_3})$
  • 小于 $x$ 且与 $x$ 互质的数的个数：$\phi(x)=x \times (1-\frac{1}{a_1}) \times (1-\frac{1}{a_2}) \times (1-\frac{1}{a_3})$
  • 比如 $12 = 2 ^ 2 \times 3 ^ 1$
  • 那么 $12$ 的约数个数为：$(2 + 1) \times (1 + 1) = 6$
  • 那么 $12$ 的约数和为：$(1 + 2 + 4) \times (1 + 3) = 28$
  • 小于 $12$ 且与 $12$ 互质的数的个数：$\phi(12)=12 \times (1-\frac{1}{2}) \times (1-\frac{1}{3})=4$