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