ブルート フォース アルゴリズムは数値の最大の素因数をどのように見つけますか?また、すべての数値をテストするよりも高速であるのはなぜですか?

Python の素因数の検索

質問:

2 部構成の質問:

1. 数値の最大の素因数を見つけるブルート フォース アルゴリズムがどのように機能するのか説明していただけますか?
2. このアルゴリズムは、単純にすべての数値をテストするアルゴリズムよりも高速であるのはなぜですか?

コード例:

<code class="python">n = 600851475143
i = 2
while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1

print(n)</code>

答え:

1.アルゴリズムの仕組み:

指定されたアルゴリズムは、2 から指定された数値 n の平方根までのすべての数値を反復処理することにより、総当たり力を使用して最大の素因数を見つけます。各数値 i について、n を剰余なしで除算できるかどうかを確認します。割り切れる場合は、n が i で割り切れなくなるまで、繰り返し n を i で割ります。次に、i を 1 だけインクリメントし、プロセスを続行します。最大の素因数が n の最終値になります。

2。アルゴリズムが速い理由:

指定されたアルゴリズムは、数値の素因数がその平方根以下になるという事実を利用しているため、単純にすべての数値をテストするよりも高速です。 n の平方根までのみ反復することで、アルゴリズムはチェックすべき潜在的な候補の数を減らし、効率を大幅に向上させます。

改良されたアルゴリズム:

提供されるコード例には、すべての場合において最大の素因数を正しく見つけることができないといういくつかの問題があります。アルゴリズムの修正版は次のとおりです。

<code class="python">def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            n //= i
        else:
            i += 1
    return n</code>

このアルゴリズムは、完全な平方や素因数が繰り返される数値であっても、最大の素因数を正しく見つけます。

以上がブルート フォース アルゴリズムは数値の最大の素因数をどのように見つけますか?また、すべての数値をテストするよりも高速であるのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。