- 368 名前：デフォルトの名無しさん mailto:sage [2007/05/20(日) 04:20:25 ]
- 友愛数を探すプログラム
「博士が愛した数式」で出てきた友愛数
友愛数の定義
ja.wikipedia.org/wiki/%E5%8F%8B%E6%84%9B%E6%95%B0
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分)
誰か高速化してくださいな。
ソース:kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/4009.txt
高速化のポイント
・約数をもっとスマートに見つける方法はないか？(これがかなり遅い)
・10の約数の和が100になるわけないので本探索のjのループに無駄が多い
かといって、どこまではしょっていいかわからない j = i / 2 〜 とか？
・あ、jをループにするから遅いんだ。yakuwaをソートして二分木探索すればいいんだ
|
 |
