07/05/20 04:20:25
友愛数を探すプログラム
「博士が愛した数式」で出てきた友愛数
友愛数の定義
URLﾘﾝｸ(ja.wikipedia.org)
Aの約数の和=B、Bの約数の和=Aのとき、A、Bは友愛数である
（ただし約数には自分自身を含めない）
例：220と284
220の約数の和=1+2+4+5+10+11+20+22+44+55+110=284
284の約数の和=1+2+4+71+142=220
とりあえず1,000,000まで探してみた。39組あった。
オイラーは60余り見つけたらしい。
が、いかんせん遅すぎる。(Athlon64 3500+で33分)
誰か高速化してくださいな。
ソース:URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
高速化のポイント
・約数をもっとスマートに見つける方法はないか？(これがかなり遅い)
・10の約数の和が100になるわけないので本探索のjのループに無駄が多い
かといって、どこまではしょっていいかわからない j = i / 2 ～ とか？
・あ、jをループにするから遅いんだ。yakuwaをソートして二分木探索すればいいんだ