Python で数値のすべての因数を効率的に見つけるにはどうすればよいですか?

Python で最大の効率で数値の因数を求める

数値のすべての因数を求めることは、特に次のような問題を扱う場合には困難なタスクになる可能性があります。多数。この記事では、Python 2.7 でこれを実現する効率的な方法について説明します。

因数分解を使用した最適なアプローチ

数値のすべての因数を見つけるには、それを分解することが重要ですその主な要因に。素因数がわかれば、残りの因数を見つけるのは簡単です。

以下のコード スニペットは、このアプローチを利用しています。

<code class="python">from functools import reduce

def factors(n):
    return set(reduce(
        list.__add__,
        ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))</code>

この関数は、数値 n を受け入れ、以下を含むセットを返します。

アルゴリズムを理解する

アルゴリズムの中核は、range(1, int(sqrt(n)) 1) if n % i == 0。この部分は因数のペアを生成します。

1 から n の平方根までの各数値 i について、n が次で割り切れるかどうかをチェックします。私は残りません。そうである場合、i と n//i は両方とも n の因数であるため、ペアに両方が含まれます。

検索範囲の最適化

検索する理由n の平方根までは、i が n の因数である場合、そのペアの因数 n//i もその範囲内で見つけなければならないということです。これにより、因子を見逃すことがなくなります。

重複の処理

完全正方形には重複した因子があるため (例: 4 には因子 2 と 2 がある)、set( ...) コード スニペットの最後で、ペアのリストから重複を削除します。これにより、一意の因数のきれいなセットを確実に取得できます。

使用例

この関数を使用するには、因数分解する数値を引数として渡すだけです。

<code class="python">result = factors(24)  # -> {1, 2, 3, 4, 6, 8, 12, 24}</code>

これは、数値 24 のすべての因数を含むセットを返します。

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