本文介绍一种时间复杂度更优的方法，通过寻找第二小的真因子（大于1的最小因子），再用原数除以它，从而直接得到第二大约数；该方法避免遍历至 n−1，仅需检查至 √n，显著提升效率。
本文介绍一种时间复杂度更优的方法，通过寻找第二小的真因子（大于1的最小因子），再用原数除以它，从而直接得到第二大约数；该方法避免遍历至 n−1，仅需检查至 √n，显著提升效率。
在解决“求正整数第二大约数（不包括自身）”的问题时，直观思路是倒序遍历 n-1 到 2，逐个检查是否为约数，并记录第二个匹配值。但这种暴力法最坏时间复杂度为 O(n)，对大数极不友好（例如 n=10⁹ 时需上亿次取模运算）。
更优策略基于约数成对出现的数学性质：若 d 是 n 的约数且 d ≤ √n，则 n // d 必为对应的大约数，且 n // d ≥ √n。因此：
- 最大约数（不包括
n自身）恒为n // p₁，其中p₁是n的最小质因子（>1）； - 第二大约数则对应
n // p₂，其中p₂是n的第二小真因子（>1，且 ≠ p₁）； - 若不存在
p₂（即n只有一个真因子 >1），需分情况处理：- 若
n = p₁²（如 25 = 5²），则约数为{1, 5, 25}，第二大约数为1； - 若
n = p₁ × q（q为质数且q > p₁，如 8 = 2×4，但 4 非质数；实际 8 的约数为{1,2,4,8}，第二大约数是4→ 对应p₁ = 2，无p₂，此时第二大约数即为p₁本身）。
- 若
以下为高效实现（Python 3.8+）：
from math import isqrt
def second_largest_divisor(n):
if n 1）
for i in range(2, isqrt(n) + 1):
if n % i == 0:
if first is None:
first = i
else:
# 找到第二个真因子，返回 n // i（即对应的大约数）
return n // i
# 未找到第二个真因子
if first is None:
return 1 # n 为质数，约数只有 1 和 n → 第二大约数为 1
else:
# first 存在，但无 second：检查 n // first 是否等于 first（即 n 为完全平方数）
if n // first == first:
return 1 # 如 25: first=5, n//first=5 → 约数集 {1,5,25} → 第二大约数为 1
else:
return first # 如 8: first=2, n//first=4 ≠ 2 → 约数集 {1,2,4,8} → 第二大约数为 4？等等——注意：此处逻辑需校准！
# ✅ 修正版（严格匹配题设逻辑与原始答案）：
def second_largest_divisor(n):
if n = 2")
first = 1 # 初始化为 1（1 总是约数，但题目要求“besides itself”，且通常不计 1？注意：题设示例 36→12，而 36 的约数（除自身）为 [1,2,3,4,6,9,12,18] → 第二大是 12，最大是 18）
# 实际题意：所有真约数（divisors 1，返回 n // i
found_first = False
for i in range(2, isqrt(n) + 1):
if n % i == 0:
if not found_first:
found_first = True
else:
return n // i # 第二个找到的 i → 对应第二大约数
# 若只找到一个真因子 i，则：
# - 若 n == i * i，则约数对称，第二大为 i（？不对：36 中 i=2,3,6；25 中 i=5，约数为 1,5,25 → 真约数为 [1,5] → 第二大是 1）
# 正确逻辑见原始答案：若 first 已设且未触发 return，则：
# 若 n // first == first → 完全平方 → 第二大约数为 1（因真约数为 [1, first]）
# 否则 → 第二大约数就是 first（如 n=8：i=2 整除，first=2；isqrt(8)=2，循环结束；n//first=4≠2 → 返回 first=2？但 8 的真约数是 [1,2,4] → 降序[4,2,1] → 第二大是 2 ✓）
# n=6：i=2 → first=2；i=3 不进循环（3>isqrt(6)≈2.4），n//2=3≠2 → 返回 2；真约数[1,2,3]→[3,2,1]→第二是 2 ✓
# n=4：i=2，first=2，n//2=2==2 → 返回 1；真约数[1,2]→[2,1]→第二是 1 ✓
# 复用原始答案结构（已验证正确）：
first = 1
for i in range(2, isqrt(n) + 1):
if n % i == 0:
if first != 1:
return n // i
first = i
if first == 1:
return 1 # n 是质数，真约数只有 1
if n // first == first:
return 1
return first
使用示例：
print(second_largest_divisor(36)) # → 12
print(second_largest_divisor(25)) # → 1
print(second_largest_divisor(16)) # → 4 （约数：1,2,4,8,16 → 真约数降序：8,4,2,1 → 第二大是 4）
print(second_largest_divisor(7)) # → 1 （质数，真约数仅 {1} → 严格说不足两个？但按定义“第二”不存在，惯例返回 1）
关键注意事项：
- 该算法时间复杂度为 O(√n)，远优于暴力 O(n)；
-
isqrt(n)（整数平方根）确保循环上界精确，避免浮点误差； - 边界情况（质数、完全平方数、小整数）均已覆盖；
- 返回值始终为正整数，且保证是
n的真约数（即且 <code>> 0）； - 若需获取全部真约数并排序取第 k 大，建议改用集合收集 + 排序，但本解法专为“第二大约数”优化，不冗余存储。
掌握这一思路，不仅能高效解决本题，也为处理因子相关问题（如约数个数、约数和、最大真约数等）提供了可复用的数学建模范式。
