本文介绍一种时间复杂度接近 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 <= 3:
return 1 # 小于4的正整数，最大真因数只有1
first = None # 第二小真因数的“候选”实际是第一个找到的 >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)，即 first
# 此时因数对为 (first, n//first)
# 若 first² == n（完全平方数），则 n//first == first，真因数中大于 first 的只有 n//first 本身，
# 所以第二大真因数应为 first（因为最大是 n//first = first，第二大退化为 first？不对！注意定义）
# ✅ 正确定义：真因数 = 正因数且 ≠ n；排序后取倒数第二个。
# 对质数：因数集 {1, n} → 真因数 {1} → 只有1个 → 第二大无定义，返回1（约定）
# 对平方数如25：因数 {1,5,25} → 真因数 {1,5} → 排序[1,5] → 第二大是1
# 对非平方如8：因数 {1,2,4,8} → 真因数 {1,2,4} → 排序[1,2,4] → 第二大是2
# 关键观察：若仅找到一个 i < sqrt(n)，则真因数包含：1, i, n//i（可能等于 i），以及可能其他 > sqrt(n) 的？
# 实际上：所有 > sqrt(n) 的真因数必为 n//i 形式，其中 i 是 < sqrt(n) 的因数。
# 所以真因数集合 = {1} ∪ {i | i∈[2,√n], n%i==0} ∪ {n//i | i∈[2,√n], n%i==0}
# 当只有一个 i 时，集合为 {1, i, n//i}
# 若 i == n//i（即 i²=n），则集合为 {1,i} → 排序后第二大是1
# 否则集合为 {1,i,n//i}，三者互异，且 1 < i < n//i → 第二大是 i
if first * first == n:
return 1
else:
return first
else:
# 找到两个不同因数 i1 < i2 ≤ √n ⇒ 对应大因数 n//i1 > 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 大因数、因数个数统计、质因数分解等经典问题。
