本文介绍一种时间复杂度接近 o(√n) 的高效算法，用于求正整数 n 的第二大真因数（即除自身外第二大的正因数），避免遍历全部范围，并通过因数配对原理优化性能。
本文介绍一种时间复杂度接近 o(√n) 的高效算法，用于求正整数 n 的第二大真因数（即除自身外第二大的正因数），避免遍历全部范围，并通过因数配对原理优化性能。
在数论中，一个正整数 n 的所有正因数总是成对出现：若 d 是 n 的因数，且 d ≤ √n，则 n/d 也是因数，且 n/d ≥ √n。因此，最大的真因数是 n 除以最小的真因数（>1），而第二大的真因数则对应于 n 除以第二小的真因数（>1）——前提是该因数存在。
原始代码从 2 到 n−1 顺序遍历，最后赋值的 result 实际上是最大的真因数（如 36 → 18），因为它按升序扫描，每次更新都覆盖为更大的因数。要获取“第二大”，朴素思路是倒序遍历（从 n−1 往下），但最坏情况仍需 O(n) 时间，对大数不友好。
更优策略是：
✅ 只需遍历至 ⌊√n⌋；
✅ 记录前两个找到的最小真因数（跳过 1）；
✅ 利用因数配对关系 d × (n/d) = n 直接推导高位因数。
以下是经过严谨边界处理的参考实现：
from math import isqrt
def second_largest_divisor(n):
if n 1 因数
second = None # 第二个找到的 >1 因数（即第二小真因数）
# 从2开始找最小真因数（跳过1）
for i in range(2, isqrt(n) + 1):
if n % i == 0:
if first is None:
first = i
elif second is None:
second = i
break # 找到第二小，立即终止
# 情况1：未找到第二小真因数
if second is None:
if first is None:
# n 是质数 → 真因数只有1 → 第二大真因数不存在，按惯例返回1
return 1
else:
# 只有一个真因数 sqrt(n) 的？
# 实际上：所有 > sqrt(n) 的真因数必为 n//i 形式，其中 i 是 n//i2 ≥ √n
# 真因数中最大的是 n//first，第二大的就是 n//second
return n // second
⚠️ 注意事项：
- 该函数默认
n > 1；若n=1，无真因数，建议前置校验；- “第二大真因数”在真因数个数 1 作为约定值（因
1恒为任何n>1的真因数）；- 时间复杂度为 O(√n)，远优于暴力 O(n)；空间复杂度 O(1)；
- 示例验证：
second_largest_divisor(36)→ 因数对：(2,18), (3,12), (4,9), (6,6) → 真因数排序[1,2,3,4,6,9,12,18]→ 第二大是12✓second_largest_divisor(25)→ 真因数{1,5}→ 第二大是1✓second_largest_divisor(8)→ 真因数{1,2,4}→ 第二大是2✓
掌握这一因数配对思想，不仅能高效解决“第二大真因数”，还可拓展至求第 k 大因数、因数个数统计、质因数分解等经典问题。
