Project Euler 005を解いてみる。「最小の倍数」

#本題:Project Euler 005
001~004まで解いてみて、いつも近道をしようとして結局遠回りをしている感が強いですが、今回も頑張っていきます。
005

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

->次の問題

考え方

1~20までで割り切れる最小の正の整数=2~20の最小公倍数
つまり答えの数は素因数として2~20までの数の素因数を全て含む。

##方法①配列2~20を作り、最大割れる数を探す。
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
2で割れる数は割ってみる
[1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8, 17, 9, 19, 10]
もう1回2で割ってみる
[1, 3, 1, 5, 3, 7, 2, 9, 5, 11, 3, 13, 7, 15, 4, 17, 9, 19, 5]
三度2で割ってみる
[1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 2, 17, 9, 19, 5]
最後にもう一度2で割ってみる
[1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5]
2~20の配列全てを2で割り切るには4回割る必要がある→答えの素因数には、2が4つ含まれる。
同様に3で割る、5で割る…と繰り返すことで答えの素因数がわかる。
あとはその素因数を乗算すれば答えになるはずです。

コード

euler005.py

def main():
    n = 20
    num_arr = np.arange(2, n + 1)  # 2~20の配列を作成
    ans = 1  # 答え用の変数
    for i in range(2, n + 1):
        mask = num_arr % i == 0  # numpyで[iで割り切れる数]に一致するboolean配列を作成
        while mask.any():  # １つでも割り切れる数がある場合
            num_arr = np.where(mask, num_arr // i, num_arr)  # 割れる数はiで割る、割れない数はそのまま
            ans *= i  # 回答に掛け算
            mask = num_arr % i == 0  # maskを更新
    print(ans)


if __name__ == '__main__':
    main()

##方法②20以下の素数pについて、p^q <= 20を満たす最大のqを考える
2~20の数で割り切れるということは、必ず20以下の素数を全て素因数に持っていると考えられます。
あとはそれぞれの素因数が最大何個ずつ必要かがわかれば答えは計算できそうです。
20以下の整数で最も2を素因数に含む数は2の4乗=16、最も3を素因数に含む数は3^2=9及びその2倍である18です。
つまり、n以下の整数のうち素因数pを最も多く含む数の1つは、pの累乗であるはずです。
よって、20以下の素数を列挙し、それぞれの素数pについて、p^q < 20となる最大のqを計算すれば答えに必要な素因数が計算できます。
素数の生成には、Project Euler 003を解いてみる。頑張って素数を早く出してみる。で作成したprime_generatorを流用してみました。

##コード

math_functions.py

import numpy as np


def prime_generator(n: int) -> int:
    """
    n以下の素数を返すgenerator
    :param n: int
    :return: int
    """
    num_arr = np.arange(2, n + 1)
    while num_arr.size > 0:
        prime = num_arr[0]
        yield prime
        num_arr = num_arr[num_arr % prime != 0]

euler005.py

from math_functions import prime_generator #自作のprime_generatorをimport


def another_main():
    n = 20
    ans = 1
    for prime in prime_generator(n): #prime_generatorで20以下の素数を生成
        i = 1
        while prime ** i <= n: #素数の累乗が20以下の間
            ans *= prime #素数を累乗していく
            i += 1
    print(ans)


if __name__ == '__main__':
    another_main()

方法②のほうが方法①より4倍ほど早いようです。理由としては、必要な素数の数があまり多くない(n=50なんかでやると答えの数がオーバーフローする)ので素数生成があまりボトルネックにならないためと考えます。
結果 232792560 main処理時間: 0.0004699230194091797 sec. another_main処理時間: 0.0001049041748046875 sec.