如何在Python中找到一个数字的最大质因数？

在 Python 中查找素因数

数论中的一个常见任务是查找数字的素因数。一种可能的方法是简单地将数字除以从 2 到其平方根的下限的所有其他数字，检查余数是否为 0。但是，这种方法的计算成本可能很高。

一种更高效的暴力方法 -下面介绍了专门用于查找数字的最大素因数的强制算法：

<code class="python">def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

该算法的工作原理是迭代所有数字直至给定数字的平方根。对于每个数字，它检查该数字是否是给定数字的因数，如果是，则将该数字除以该因数。该算法一直持续到该数字不再能被该范围内的任何数字整除，并且剩余的数字是最大的素因数。

<code class="python">largest_prime_factor(600851475143)
# Output: 6857

或者，要查找一个数的所有素因数：

<code class="python">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</code>

以上是如何在Python中找到一个数字的最大质因数？的详细内容。更多信息请关注PHP中文网其他相关文章！