Project Euler 5
問題
以下の任意の正整数で割り切れる最小の正整数を と置いて を求める。
記号
[ 表記 ]:[ 返り型 ]:[ 説明 ]
:整数:切り捨て除算、 を超えない最大の整数
:整数: を超えない最大の整数、ガウス関数
解法
正整数 が全て異なる素数列 と非負整数列 によって と書ける時、 が で割り切れる必要十分条件は任意の で が成り立つことである。
よって、正整数 が 以下の任意の正整数で割り切れるためには、 を 以下の正整数の素因数に成り得る数の集合として、 に対して を 以下の正整数を素因数分解して現れる最大の の指数とした時、 を用いて と書ける必要がある。 は全ての について狭義単調増加なので、そのような最小の は である。
については素数の集合なので一般的にあまり具体的には書き下せないが、 以下の全ての素数を含み、 を超える全ての素数を含まないことから 以下の全ての素数の集合として与えられることは分かる。 については に対して具体的に得られ、
から となる。
よって求める正整数は
解
で
より
近似手法
以下の素数の個数と 番目の素数についてはそれぞれ近似式が知られているので、それで の近似式も得られるが、(筆者が知る近似法では)小さい素数に関する近似値の誤差が大きく、それらの積を含む の近似精度は符号が変わるレベルで悪い。