题解 | 质数因子

咋基本上所有人都在说质因子不会超过平方根。。。这是错的

106=2*53，

106有质因子53，显然大于根号106

​

93938=3613 × 2 × 13

93938有质因子3613，显然大于根号93938（约等于306）

正确表述是：

一个合数至少有一个不超过它算术平方根的质因数。

而相关代码能正确工作的原理是：任何合数，在不断除掉所有不超过平方根的因子之后，剩下的数要么是 1，要么一定是一个质数。证明为：

试除质因子的循环结束后，有两种情况：

情况 1：t == 1

• 所有质因子都 ≤ √n
• 已经被完全分解

情况 2：t > 1

这时要证明两件事：

（1）t 一定是质数

假设 t 是合数：t = a × b

那么必有：a ≤ √t ≤ √n

但：所有 ≤ √n 的因子在 for 循环中都已经被除尽，矛盾

所以 t 不可能是合数，只能是质数。

（2）t 不可能再有两个因子

如果还剩两个 > √n 的因子：p × q > √n × √n = n，矛盾

所以只可能剩一个。