python~素数列挙(エラトステネスの篩)と素因数分解~

初めに

こんにちは、keymaleです。今回はpythonでの素数数え上げです。通常のやり方から、高速数え上げ(エラトステネスの篩←ふるいって読みます)を実装します。atcoderのD問題で2回目にこの素数数え上げに関する問題が出たので、備忘録として書いておきます。素因数分解も紹介しておきます。

通常の素数列挙

通常の方法は以下になります。

def get_primenumber(number):
    prime_num = [2]
    for i in range(3,number+1,2):
        if all(i%j != 0 for j in  prime_num):
            prime_num.append(i)
    return prime_num
                

2は自明の素数として、3から2個ずつ、3,5,7,9,11…の順に自身より小さい素数で割れるか計算して、すべて割れなければ、新たな素数としてリストに追加します。

高速素数列挙(エラトステネスの篩)

次にエラトステネスの篩です。

def get_primenumber(number):#エラトステネスの篩
    prime_list = []
    search_list = list(range(2,number+1))
    #search_listの先頭の値が√nの値を超えたら終了
    while search_list[0] <= math.sqrt(number):
      #search_listの先頭の値が√nの値を超えたら終了
      #search_listの先頭をprime_listに入れて、先頭をリストに追加して削除
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        #head_numの倍数を除去
        search_list = [num for num in search_list if num % head_num != 0]
    #prime_listにsearch_listを結合
    prime_list.extend(search_list)
    return prime_list

調べたい最大値まで1ずつ増えるリストを作成し(最小値は2)、リストの最小値でリストをすべて割っていき、割り切れるものは削除し、割っていた数を素数リストに追加します。そして、削除後のリストの最小値で、またリストを割っていき、割り切れたものを削除して、割っていた値を素数リストに追加。これを√nまで繰り返します。

素因数分解

素因数分解は素因数分解したい数nに対して2から√nまで順番に割り切れなくなるまで割って、割った回数を出力します。コードは以下の通りです。

def factrization_prime(number):
    factor = {}
    div = 2
    s = math.sqrt(number)
    while div < s:
        div_cnt = 0
        while number % div == 0:
            div_cnt += 1
            number //= div
        if div_cnt != 0:
            factor[div] = div_cnt
        div += 1
    if number > 1:
        factor[number] = 1
    return factor
例えば180を素因数分解すると

factrization_prime(180)
{2: 2, 3: 2, 5: 1}

のように辞書型で2^2*3^2*5^1が出力されていることがわかります。