如何高效寻找满足k²>n的正整数n的最小因数k？

先改基础逻辑：从2开始遍历，找到就停 #

你原来从sqrt(n)倒着遍历的思路完全没必要，反过来从2开始遍历到sqrt(n)，一旦找到能整除n的数，直接拿到一对因数（当前数和n//当前数），立刻终止循环就行。比如你说的15838，遍历到2就找到因数了，循环1次搞定，根本不用跑几千次。

伪代码示例：

def get_factors(n):
    factors = []
    # 遍历到sqrt(n)就行，超过的话因数会重复
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            factors.extend([i, n//i])
            break  # 只找一个因数对的话直接break，要全因数就去掉
    # 如果没找到，说明n是质数
    if not factors:
        factors.append(n)
    return factors

再砍一半循环：跳过偶数（除了2） #

先单独检查2是否是因数，之后只遍历奇数，这样循环次数直接减半，对奇数的处理效率提升明显。

优化后的伪代码：

def get_factors(n):
    factors = []
    # 先处理2的情况
    if n % 2 == 0:
        factors.extend([2, n//2])
        return factors
    # 从3开始，步长设为2，只遍历奇数
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            factors.extend([i, n//i])
            break
    if not factors:
        factors.append(n)
    return factors

更大的数？试试Pollard's Rho算法 #

如果要处理百万级以上的大数，试除法还是不够快，Pollard's Rho算法是专门针对大整数分解的概率算法，效率比试除法高得多，尤其适合分解像15838这种半质数（两个质数乘积）的情况。它通过随机数和判圈逻辑快速找到非平凡因数，时间复杂度远低于O(sqrt(n))。

核心思路的伪代码：

import random
from math import gcd

def pollards_rho(n):
    # 先排除小质数情况
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    # 随机生成函数，找循环计算gcd
    while True:
        c = random.randint(1, n-1)
        f = lambda x: (pow(x, 2, n) + c) % n
        x, y, d = 2, 2, 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = gcd(abs(x - y), n)
        if d != n:
            return d

# 递归分解得到所有因数
def factorize(n):
    if n == 1:
        return []
    d = pollards_rho(n)
    if d == n:
        return [n]
    return factorize(d) + factorize(n//d)

用这个方法分解大的半质数，速度会比试除法快几个数量级。

内容的提问来源于stack exchange，提问作者NekomiyaKasane