Python で素因数を見つける

1. 素因数分解の概要
2. Python で素因数を見つけるためのさまざまなアプローチ

このチュートリアルでは、Python で素因数分解を実行する方法を示します。

素因数分解の概要

数学では、数の因数とは、与えられた数を割って残りがゼロになる数です。

素数は、2つの要素 (1つと数自体) のみを持つ一意の数です。 そのような数の例としては、3、7、11、13 などがあります。

素因数分解とは、乗算して元の数を構成するすべての素数を見つけることを指します。 数 6 の簡単な例を考えることができます。

この数を素因数分解すると、2 と 3 の 2つの因数が得られます。

Python で素因数を見つけるためのさまざまなアプローチ

指定された数の素因数をさまざまな方法で見つけることができます。 この記事では、以下に示す 3つの方法について説明します。

• カスタム関数を作成する
• エラトステネスのふるいを使う
• primefac モジュールを使用する

Python でカスタム関数を作成することから始めましょう。

素因数分解を実行するカスタム関数

数学では、最も基本的な素因数分解のアプローチは割り算の繰り返しです。 数を素数で繰り返し割ります。 これは、ネストされたループを使用して Python で実装できます。

最初のループは、数値が素数かどうかを判断します。 2 番目のループは、この素数と指定された数値を除算します。

余りがゼロの場合、素数をリストに追加します。 関数は最終的なリストを返します。 以下のコードを参照してください。

def p_factorization(n):
    i = 2
    lst = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            lst.append(i)
    if n > 1:
        lst.append(n)
    return lst


print(p_factorization(20))

出力：

[2, 2, 5]

上記の例では、20 の素因数分解を返しました。 除算の // 演算子は、返される剰余が整数であることを保証します。

エラトステネスのふるいを使って素因数分解を行う

エラトステネスのふるい アルゴリズムは、指定された数値以下のすべての素数を返します。

指定された数値より小さい値をマークし、素数の 2 乗で割り切れて、指定された数値より小さいすべての素数を返します。

これを使用して、Python で素因数分解を実行できます。 まず、必要な数より下の素数を見つけ、次にそれらを指定された数で割り、その素因数分解を確認します。

例として、次のコード フェンスを参照してください。

def sieve_of_erast(number):
    maximum = number + 1
    d = dict()
    for i in range(2, maximum):
        d[i] = True

    for i in d:
        factors = range(i, maximum, i)
        for f in factors[1:]:
            d[f] = False
    lst = [i for i in d if d[i] == True]
    return lst


def p_factorization(number):
    x = number
    res = []
    lst = sieve_of_erast(number)
    i = 0
    while i < len(lst):
        if x % lst[i] == 0:
            x = x // lst[i]
            res.append(lst[i])
            i = 0
            if x == 1:
                break
        else:
            i = i + 1
    return res


print(p_factorization(20))

出力：

[2, 2, 5]

上記のコード例では、最初に 20 以下の素数を見つけるために エラトステネスのふるい を実装する関数を作成します。

次に、この素数のリストを使用して素因数分解を返す別の関数を作成します。

primefac モジュールを使用して素因数分解を実行する

primefac モジュールは、素数に関する計算を実行するために使用されます。 大規模な計算を効率的に処理できます。

このモジュールの primefac() 関数を素因数分解に使用できます。 list コンストラクターを使用してリストに変換できるジェネレーター オブジェクトを返します。

以下のコードを参照してください。

import primefac

print(list(primefac.primefac(20)))

出力：

[2, 2, 5]