素因数分解，エラトステネスの篩をPythonで実装して関数化する

hirohirohirohiros.hatenablog.com

概要

　整数を引数にとり素因数分解し，keyを素因数，valueを指数としたdictを返す関数を作ります．素因数分解には試し割り方を使います．計算量はO()です．
　更に，この関数に素数を入れると要素1かつvalue=1のdictが返ってくるので，素数判定にも使えます．
　また，同じ素数関連ということでエラトステネスの篩も実装します．この関数は0からNまでの整数に関して，整数iが素数ならi番目がTrue，合成数ならi番目がFalseのリストを返す関数です．これでNまでの素数を列挙することになります．計算量はO()です．素因数分解関数で素数を判定してNまで素数を列挙する方法だとO()なのでエラトステネスの篩の速さが良く分かります．

アルゴリズムの概要

素因数分解

　試し割り方を使います．試し割り方はとにかくいろいろな値で割れるだけ割り，その割れた回数を数えることで素因数分解します．2以外の偶数は，既に2で割れるだけ割ってるので，それ以外の偶数で割り切れる可能性は0なので割らなくて良いです．よって2,3,5,7,9……と2と奇数について割れるだけ割っていきます．既に3で割っているので9も割らなくて良いように思いますがそのためには9が合成数である事を調べる必要があり，余計に時間が掛かってしまいます．よって2と奇数について割っていき，割れた回数を記録します．
　から，以上の素因数は最大でも一つしかないことが分かります．よって割る数はまでで良いことが分かります．まで割って，まだ値が1より大きい値なら，それも素因数の一つであることに注意します．

エラトステネスの篩

　0からNまでTrueが入ったリストを用意します．i番目がFalseだとそれは素数ではありません．0と1は素数ではないのでFalse，2は素数なのでTrueにします．
　このリストでi番目がTrueの時，その倍数は素数ではありません．よってi*2番目，i*3番目...は全てFalseにします．i*n番目がNを超えたら処理を終え，i+=1としてi番目がTrueか確認します．i番目がTrueならi*2番目, ...をFalseにし...と繰り返します．iがまで行ったら処理を終了します．最終的にTrueだったものは素数になっています．

pythonコード

素因数分解

def prime_fact(x):
    """素因数分解

    素数判定も可能
    計算量: O(n**(1/2))

    Args:
        x (int): 素因数分解する整数

    Returns:
        dict: {素因数:指数, 素因数:指数, ...}    
    """
    prime_dict = {}
    p = 2
    while p**2 <= x:
        if x % p == 0:
            prime_dict.setdefault(p, 0)
            prime_dict[p] += 1
            x //= p
        else:
            p = 3 if p == 2 else p + 2
    if x != 1:
        prime_dict.setdefault(x, 0)
        prime_dict[x] += 1
    return prime_dict

エラトステネスの篩

def erato_sieve(x):
    """エラトステネスの篩

    0からxまでの素数を返す
    計算量: O(n loglog n)

    Args:
        x (int): 素数判定をしたい数の最大値

    Returns:
        list: i番目が素数ならTrue, そうでないならFalse
    """
    prime_list = [True]*(x+1)
    prime_list[0] = False
    prime_list[1] = False
    p = 2
    while p**2 <= x:
        if not prime_list[p]:
            p += 1
            continue
        
        i = p*2
        while i <= x:
            prime_list[i] = False
            i += p
        p += 1

    return prime_list