📖 埃拉托斯特尼筛法
质数的倍数一定不是质数！所以从 2 开始，把每个质数的倍数都标记成合数，最后没被标记的数就都是质数。
数字格 绿色 = 筛出来的质数，灰色 = 合数
质数
合数
正在看
控制台
速度
erato.cppC++
📖 欧拉筛（线性筛）
埃氏筛有个小缺点：一个合数可能被标记好多次，比如 12 会被 2 和 3 各标记一次。欧拉筛规定：每个合数只被它的最小质因数筛掉一次，每个格子右上角的小标签就是"被谁筛掉的"！
数字格 右上角小标签 = 用哪个质数筛掉的它
质数
合数（被筛掉）
控制台
速度
euler.cppC++
📖 质因数分解（唯一分解定理）
任何合数都能唯一分解成质因数的乘积，比如 90 = 2 × 3 × 3 × 5。方法：先用埃氏筛筛出质数表，再从小到大试除，一边除一边记次数。
分解过程
当前 n（被不断除小）
90
90 = 2^0 × 3^0 × 5^0
质数表 黄色 = 正在试除
控制台
速度
分解结果
90 = 2^1 × 3^2 × 5^1factor.cppC++
📖 n! 的质因数分解（勒让德公式）
n! 里质数 p 一共出现多少次？数一数：1~n 里 p 的倍数有 n/p 个，每个至少贡献 1 个 p；p² 的倍数再多贡献 1 个，有 n/p² 个……所以 p 的个数 = n/p + n/p² + n/p³ + …（加到哪一项变成 0 为止）。这就是勒让德公式！
质数表 黄色 = 正在统计的质数
勒让德公式算一算 每步高亮的是当前累加的项
笨办法：把 1~n 每个数都分解一遍再统计（对比一下）
控制台
速度
n! 分解结果
13! = 2^10 × 3^5 × 5^2 × 7^1 × 11^1 × 13^1factorial.cppC++