Project Euler 5 - Essaytial Machine Learning

問題

　 $N$ 以下の任意の正整数で割り切れる最小の正整数を $PE5(N)$ と置いて $PE5(20)$ を求める。

記号

[ 表記 ]：[ 返り型 ]：[ 説明 ]
$y // x$ ：整数：切り捨て除算、 $y / x$ を超えない最大の整数
$\lfloor x \rfloor$ ：整数： $x$ を超えない最大の整数、ガウス関数

解法

　正整数 $m, n$ が全て異なる素数列 $p_1, \dots, p_k$ と非負整数列 $a_1, \dots, a_k, b_1, \dots, b_k$ によって $m = p_1^{a_1}\dots p_k^{a_k}, n = p_1^{b_1}\dots p_k^{b_k}$ と書ける時、 $n$ が $m$ で割り切れる必要十分条件は任意の $i = 1, \dots, k$ で $a_i \leq b_i$ が成り立つことである。

　よって、正整数 $n$ が $N$ 以下の任意の正整数で割り切れるためには、 $\Pi(N)$ を $N$ 以下の正整数の素因数に成り得る数の集合として、 $p \in \Pi(N)$ に対して $\sigma ^ N_p$ を $N$ 以下の正整数を素因数分解して現れる最大の $p$ の指数とした時、 $\tau_p \geq \sigma ^ N_p$ を用いて $n = \prod _ {p \in \Pi(N)}p^{\tau_p}$ と書ける必要がある。 $\prod _ {p \in \Pi(N)}p^{\tau_p}$ は全ての $\tau_p$ について狭義単調増加なので、そのような最小の $n$ は $\prod_{p \in \Pi(N)}p^{\sigma ^ N_p}$ である。

　 $\Pi(N)$ については素数の集合なので一般的にあまり具体的には書き下せないが、 $N$ 以下の全ての素数を含み、 $N$ を超える全ての素数を含まないことから $N$ 以下の全ての素数の集合として与えられることは分かる。 $\sigma ^ N_p$ については $p$ に対して具体的に得られ、

$\displaystyle p^{\lfloor\log_p(N)\rfloor} \leq N = p^{\log_p(N)} \lt p^{\lfloor\log_p(N)\rfloor+1}$