如何優化 Python 中尋找素因數的強力演算法?

Mary-Kate Olsen
發布: 2024-11-07 19:09:03
原創
235 人瀏覽過

How can you optimize the brute-force algorithm for finding prime factors in 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中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!