今日の約数(終)
素因数分解の結果をつかって舐める方式ではどう考えても速度に限界が出る。しょうがないから約数の数に特化してちょっと作ってみようかなと思ってたら、この問題の元となったページ*1で進展があり解決してた。もたもたしてたらこのざまだよまったく。
とは言えこのままってのも悔しいので、遅ればせながらさくっと作ってみた。最大値までの配列を作り、そこに約数の数を埋めていく方式。配列は1の約数の数1と、それ以外の数の約数未確定として0で埋めておく。詳細は省略するが、下からスキャンして配列の値が0ならば素数と判定して、約数の数2を代入してから、既に約数の数が確定している数にその素数のn乗を掛けた値の約数の数を埋めて行く*2。
今回は約数の数が最大になるケースを求めるのが目的なので、新しい素数が登場する度にその素数を1個掛けてその値が最大値を超えたところでテーブルを埋めるのを止める。多分もっと前に止めて良いポイントがあると思われるが*3、良いアイディアもなく断念。
とりあえず、7桁まではなんとか出力するプログラムが出来た*4。残念ながらWindows専用なので、試しにWebでも動くようにとJavaScriptに移植してみたが、こちらは6桁あたりで動作が怪しくなるのと、ソース丸見えで恥ずかしいので公開はなし。
