本文介绍一种时间复杂度为 o(√n) 的高效算法，用于找出正整数 n 除自身外的第二大正因数（如 36 的第二大真因数是 12），避免遍历全部范围，并正确处理完全平方数、质数幂等边界情况。
本文介绍一种时间复杂度为 o(√n) 的高效算法，用于找出正整数 n 除自身外的第二大正因数（如 36 的第二大真因数是 12），避免遍历全部范围，并正确处理完全平方数、质数幂等边界情况。
在初学循环与因数判断时，常会写出从 2 到 n-1 逐个检查的暴力方法——例如原代码中 for i in range(2, n) 找到最后一个能整除 n 的 i，结果实为最大真因数（即 n // 最小真因数），而非题目所求的第二大真因数。对 36 来说，该方法输出 18（即 36 // 2），但我们需要的是 12（即 36 // 3），这提示我们：第二大真因数 = n ÷ 第二小真因数（≥2）。
因此，高效策略是：仅遍历 [2, ⌊√n⌋]，从小到大寻找 n 的真因数，并记录前两个发现的因数。一旦找到第二个因数 i，立即返回 n // i ——它就是对应的最大配对因数，且因 i 是第二小真因数，n//i 必为第二大真因数。
但需严谨处理以下边界情形：
- 若
n是质数（如7）：无真因数 → 无第二大真因数（按题设隐含n > 1且至少有两个真因数？实际应定义行为；本实现默认返回1当仅有一个小因数且其平方等于n，或直接返回首个小因数）； - 若
n是质数的平方（如25 = 5²）：唯一小因数5，此时n//5 = 5，但第二大真因数应为1（因真因数集为{1,5}，排序后为[1,5]，第二大是1）； - 若
n是质数的立方（如8 = 2³）：小因数有2，下一个因数4出现在√8 ≈ 2.8之后，故只找到first = 2；此时第二大真因数实为n // first = 4？但真因数为{1,2,4}→ 排序[1,2,4]，第二大是2—— 这正是代码中return first的逻辑依据。
参考实现如下（使用 math.isqrt 确保整数平方根，兼容 Python ≥3.8）：
from math import isqrt
def second_largest_divisor(n):
if n <= 1:
raise ValueError("n must be greater than 1")
first = 1 # will store the smallest proper divisor >= 2
for i in range(2, isqrt(n) + 1):
if n % i == 0:
if first != 1:
return n // i # found second smallest divisor i → n//i is second largest
first = i
# Only one small divisor found (or none)
if first == 1:
return 1 # n is prime: only proper divisor is 1 → second largest doesn't exist; by convention, return 1
# first is the smallest proper divisor
# Check if n == first * first (perfect square)
if n == first * first:
return 1 # e.g., n=25 → divisors: [1,5,25], proper: [1,5] → second largest is 1
return first # e.g., n=8 → small divisors up to √8: only 2 found → proper divisors: [1,2,4] → second largest is 2✅ 正确性验证：
-
second_largest_divisor(36)→ 遍历i=2（记first=2），i=3（触发return 36//3 = 12）✔ -
second_largest_divisor(25)→i=5是唯一因数，且25 == 5*5→ 返回1✔ -
second_largest_divisor(8)→i=2是唯一 ≤√8 的因数，8 != 2*2→ 返回first=2✔（真因数{1,2,4}，第二大为2）
⚠️ 注意事项：
- 该函数假设输入为大于 1 的正整数；
- 时间复杂度从 O(n) 优化至 O(√n)，对大数（如百万级）提升显著；
- 不依赖额外存储，空间复杂度 O(1)；
- 若需支持
n=1或负数，应前置校验并明确定义语义。
掌握“因数成对出现且关于 √n 对称”这一数学性质，是优化因数相关算法的关键思维跃迁。
