Python で素因数を見つけるためのブルート フォース アルゴリズムを最適化するにはどうすればよいでしょうか?

Python での素因数の検索: 総合ガイド

素因数の決定は、数論の基本的なタスクです。最大の素因数を見つけるアプローチの 1 つは、ブルート フォース アルゴリズムを使用することです。ただし、すべてのアルゴリズムが同じように作成されているわけではありません。

総当たりアルゴリズム

一般的に使用されるアルゴリズムの 1 つは、元の値を均等に分割する数値が見つかるまで段階的に数値をテストすることです。番号。コード例を考えてみましょう。

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

このアルゴリズムは、見つかった素因数を格納する「factors」と呼ばれるリストを維持します。最後に n が 1 より大きい場合、それは最終的な素因数を示し、リストに追加されます。

結論として、効率的な素因数分解アルゴリズムを選択することがパフォーマンスにとって重要です。最適化された総当たりアルゴリズムにより速度が大幅に向上し、完全因数分解アルゴリズムにより指定された数値の完全な素因数分解が可能になります。

以上がPython で素因数を見つけるためのブルート フォース アルゴリズムを最適化するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。