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

Linda Hamilton
リリース: 2024-11-07 07:49:02
オリジナル
281 人が閲覧しました

How to Find the Largest Prime Factor of a Number in 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 サイトの他の関連記事を参照してください。

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート