Python で数値の最大の素因数を見つけるにはどうすればよいですか?

Python で素因数を見つける

数論における一般的なタスクは、数値の素因数を見つけることです。考えられる方法の 1 つは、数値を 2 から平方根の底までの 1 つおきの数値で単純に割り、余りが 0 かどうかを確認することです。ただし、このアプローチは計算コストが高くなる可能性があります。

より効率的なブルート特に数値の最大の素因数を見つけるための強制アルゴリズムを以下に示します。

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

このアルゴリズムは、指定された数値の平方根まですべての数値を反復処理することによって機能します。数値ごとに、その数値が指定された数値の因数であるかどうかを確認し、該当する場合はその数値を因数で除算します。アルゴリズムは、数値が範囲内のどの数値でも割り切れなくなり、残りの数値が最大の素因数になるまで続行されます。

<code class="python">largest_prime_factor(600851475143)
# Output: 6857

あるいは、数値のすべての素因数を見つける場合:

<code class="python">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</code>

以上がPython で数値の最大の素因数を見つけるにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。