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