质因数分解的快速算法

提出分解大数的需求，点出本课要学的快速算法。

• 把 360 分解成质因数
• 普通方法为什么慢
• 本课目标：更快更聪明地分解

在讲解之前先估计朴素试除法的检查次数，暴露先验想法。

• 预测 97 需要试除到几
• 先凭直觉选择答案
• 带着预测进入算法分析

建立最直接的分解模型：从 2 开始逐个尝试。

• 从 2 开始逐个检验
• 能正确分解但试除次数多
• 对 n 需要检查 n-1 次

用因子成对的规律解释为什么无需试到 n-1。

• 因子成对出现
• 若 d 是因子，n/d 也是因子
• 较小的因子必定 ≤ √n

调节 n，观察试到 n 和试到 √n 的检查次数差距。

• 调节 n 看检查次数
• 对比 limit=n 和 limit=√n
• 观察因子成对出现

检验对 √n 边界的理解。

• 判断 101 需要检查到哪里
• 选出最小充分检查范围
• 巩固因子成对的概念

引入用质数表缩减候选除数的思路。

• 合数候选可以跳过
• 用质数表减少无效试除
• 通常用埃氏筛预先生成质数表

讲解找到一个因子后如何高效处理余下的商。

• 找到一个因子后继续分解商
• 同一个质数可能重复出现
• 从当前质数继续而非重头开始

用优化步骤完整分解 180，并写出质因数乘积。

• 按优化步骤完成试除顺序
• 写出 180=2²×3²×5
• 应用 √n、质数候选和继续除法

汇总朴素法、√n 法和质数候选法的效率差异。

• 朴素 n 次 vs √n 次 vs 只用质数
• [Table] 方法对比：检查范围、次数、适用场景
• 核心口诀：成对因子、√n 边界、质数候选