如何优化 Python 中查找素因数的强力算法？

在 Python 中查找素因子：综合指南

确定素因子是数论中的一项基本任务。找到最大质因数的一种方法是通过强力算法。然而，并非所有算法都是平等的。

暴力算法

一种常用的算法涉及逐步测试数字，直到找到一个可以整除原始数字的数字数字。让我们考虑一个示例代码：

n = 600851475143
i = 2
while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1

print(n)

此代码搜索 600851475143 的最大素因数。但是，它效率低下，大约需要 0.01 秒才能完成。

优化暴力算法

暴力算法的改进版本可以显着减少运行时间：

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

一旦 i 超过 n 的平方根，该算法就会终止，这有效地消除了测试许多不必要的数字。因此，运行时间大大减少，对于相同的输入，大约需要 388 微秒即可完成。

完成素数分解

如果目标是获得完整的素数因式分解数字时，需要对算法稍作修改：

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

此算法维护一个名为“因子”的列表，用于存储找到的质因数。当 n 最后大于 1 时，表示最终的素因数，然后将其添加到列表中。

综上所述，选择高效的素因数分解算法对于性能至关重要。优化的暴力算法显着提高了速度，而完全因式分解算法则提供给定数字的完全素数分解。

以上是如何优化 Python 中查找素因数的强力算法？的详细内容。更多信息请关注PHP中文网其他相关文章！