裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

完全数を探せ

2015年03月11日 | ブログラミング

「10000 以下の最大の完全数を答えよ」ということなのだが,完全数は小さい方から順に,6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216, ... ということは,ちょっと調べるとすぐ分かる。
「それをいっちゃ~,おしめえよ!」なので,以下のプログラム

n = 10000
repeat {
  m = 1:n # その数までの自然数
  m = m[n %% m == 0] # 割りきれるなら約数(その数自身も含む)
  if (sum(m) == 2*n) { # 「その数の約数の和が,その数の2倍」が完全数の定義
    print(n) # 見つかったらプリントしてループから脱出
    break
  }
  n = n-2 # 完全数は,(今のところ)偶数であるという事実を利用
}

0.4 秒ほどで,8128 が表示される。
(ideone では 1.1 秒ほどかかる)

以下のようにすれば,所要時間は半分となる。

n = 10000
repeat {
  m = 1:(n/2) # その数の半分(約数 2 の相棒)までの自然数(28 なら,約数 2 と 14 の関係)
  m = m[n %% m == 0] # 割りきれるなら約数(その数自身を除く)
  if (sum(m) == n) { # 「その数の約数(その数自身を除く)の和が,その数に等しい」が完全数の定義
    print(n) # 見つかったらプリントしてループから脱出
    break
  }
  n = n-2 # 完全数は,(今のところ)偶数であるという事実を利用
}

コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

PVアクセスランキング にほんブログ村

PVアクセスランキング にほんブログ村