一、基本思想

费马分解法适用于分解两个素数因子接近的奇数合数。
它基于这样一个数学事实：

$ n = a^2 - b^2 = (a+b)(a-b) $

只要我们能找到整数 $ a, b $，使得 $ n = a^2 - b^2 $，就能分解 $ n $。

二、具体步骤

  1. 起点：
    给定一个奇数合数 $ n $。
    （偶数可以直接分解出因子 2。）
  2. 选择 $ a $：
    从 $ \lceil \sqrt{n} \rceil $ 开始，因为如果 $ a^2 < n $，那么 $ b^2 $ 会是负数，不成立。
    也就是说，最小的候选 $ a $ 是不小于 $ \sqrt{n} $ 的整数。
  3. 计算 $ b^2 $：

$ b^2 = a^2 - n $

如果 $ b^2 $ 不是完全平方数，就让 $ a = a+1 $，继续尝试。

  1. 得到分解：
    当 $ b^2 $ 是完全平方数时，得到 $ b = \sqrt{a^2 - n} $。
    然后：

$ n = (a-b)(a+b) $

就得到了分解因子。

三、举例

假设 $ n = 5959 $。

  1. $ \sqrt{5959} \approx 77.2 $，所以从 $ a=78 $ 开始。
  2. $ a=78 $：

$ b^2 = 78^2 - 5959 = 6084 - 5959 = 125 \quad (\text{不是平方数}) $

  1. $ a=79 $：

$ b^2 = 79^2 - 5959 = 6241 - 5959 = 282 \quad (\text{不是平方数}) $

  1. $ a=80 $：

$ b^2 = 6400 - 5959 = 441 = 21^2 $

找到了！
所以：

$ 5959 = (80-21)(80+21) = 59 \times 101 $