如何在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中文網其他相關文章！