Project EulerのProblem12番
三角数で約数が500より多い(つまり5001以上)ものはいくつ?
まあ,三角数を求めるところは工夫の余地無い気がしますが,
約数を探すところで,ナイーブに1から順番に割れるかどうか?みたくやったらすごく遅くて回答出る前にこっちの我慢の限界.
最適化するな.まだするな.やれ.
というわけで最適化(?)
例えば10を2で割れたなら,その商である5でも割れるんだから,
何も10の約数を探すのに1,2,3,4,5,6,7,8,9,10で割ってみないで,
1で割れる→10でも割れる 10より小さい範囲を探す
2でも割れる→5でも割れる 5より小さい範囲を探す
3,4では割れない.よって4つ.
というコード.5秒.思ったより速くない.
natural f12() { natural triangle = 0; int divnum = 0; natural upper = 0; for(natural i=1; ;++i) { triangle+=i; divnum=0; upper = triangle; for(natural j=1; j<upper; ++j) { if(!(triangle%j)) { upper = triangle/j; divnum+=2; } } if(divnum > 500) { break; } } return triangle; }
小さい数字でちゃんと動くか知りません.
ちなみに,こういうのをネットで検索してヒントを得るのは主義に反しているので余りやらないんですが,
解いてから色々見ていると,約数じゃなくて素因数分解を前提にしている回答が多い気がしました.
でも,問題には28の場合,1,2,4,7,14,28と明らかに素因数分解ではないですし,どうなんでしょう.
それでもうまくいくものなんですかね.ちゃんと読んで無いですけど.
あと,親切にも日本語に問題を翻訳してくれているページがあるんですね.
僕の場合,英語を読むのに掛かる時間が結構長いので助かります.
いや,これも英語の練習だから!逃げちゃ駄目だ!
うーん,こんなところで詰まるのでは先が思いやられるなぁ.
別に目標とか無いけど.