【初心者歓迎】C/C++室 Ver.37【環境依存OK】

【初心者歓迎】C/C++室 Ver.37【環境依存OK】 at TECH

368:デフォルトの名無しさん
07/05/20 04:20:25
友愛数を探すプログラム

「博士が愛した数式」で出てきた友愛数
友愛数の定義
Wikipedia項目ﾘﾝｸ
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をソートして二分木探索すればいいんだ

次ページ

続きを表示

1を表示