Pythonで高速に素数判定、素因数分解を行う方法を紹介します。

まえがき

現在高専に通っている16歳です!
学習の成果の書き出しや知識の共有をしたいと思っています。
よろしくお願いします!

目的

AtCoderなどの競技プログラミングやその他の実装の時に素数判定、素因数分解をする場面があると思いますが、そんな時に高速な素数判定、素因数分解を行うコードをわざわざ書きたくないのでここに書いておくことにしました。

素数判定

nが合成数のとき、√n以下で割り切れることを用いました。

prime.py

from math import sqrt

def is_prime(n):
    if not isinstance(n, int):
        return False
    elif n < 2:
        return False

    for i in range(2, int(sqrt(n))+1):
        if n % i == 0:
            return False
    return True


print(is_prime(12))       # => False

関数の最初の条件式では引数が整数でない、もしくは2未満であるかを判断します。

そして、その下のfor文では2から√nまでの数で割れるかを試して、割れたら False を返し、最終的に割れなかったら True を返します。

素因数分解

素因数を列挙する方式

prime.py

from math import sqrt

def factorization(n):
    factors = []
    if n < 1:
        return [-1]
    elif not isinstance(n, int):
        return [-1]
    elif n == 1:
        return [1]

    n1 = n
    for i in range(2, int(sqrt(n))+1):
        if n1 % i == 0:
            while n1 % i == 0:
                n1//=i
                factors.append(i)
                if n1 == 1:
                    return factors
    if n1 != 1:
        factors.append(n1)
        return factors
    elif factors == []:
        return [n]



result = factorization(120)
print(result)                # => [2, 2, 2, 3, 5]

まずは列挙できるように素因数を入れる配列を作成します。
ちなみに配列の要素の追加は遅いのであまり使いたくないですが、素因数の数を素早く計算するすべがまだ見つかってないのでやむを得ないです。

そして、1未満の数、非整数を条件文によってはじき出します。ここでは [-1] を戻り値に設定して判別がつくようにします。そして1の時は [1] を出力しておくことにします。

下のfor文ですが2から√nまで回して、nを代入したn1がiで割り切れた場合にn1がiで割れなくなるまで割り続けます。そして、割ると同時にiを配列に追加していき、forが回り終わったら、素因数が入った配列を返します。

素因数分解を指数で表記する方式

prime.py

from math import sqrt

def factorization_index(n):
    factors = []
    if n < 1:
        return [[-1]]
    elif not isinstance(n, int):
        return [[-1]]
    elif n == 1:
        return [[1]]

    n1 = n
    for i in range(2, int(sqrt(n))+1):
        if n1 % i == 0:
            count = 0
            while n1 % i == 0:
                n1//=i
                count += 1
            factors.append([i, count])
            if n1 == 1:
                return factors
    if n1 != 1:
        factors.append([n1, 1])
        return factors
    elif factors == []:
        return [n, 1]


result = factorization_index(120)
print(result)                # => [[2, 3], [3, 1], [5, 1]]

全体的に素因数を列挙する方式と似てますが、whileの中身で何回iで割れるかを数えてそれを指数の部分として返します。

最後に

拙い文章でしたが読んでいただきありがとうございます。まだまだ技術は未熟ですが上達するようにアドバイスなどもお願いします!