Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
5
Help us understand the problem. What is going on with this article?
@gushwell

C#:メルセンヌ素数を利用して完全数を求める

More than 3 years have passed since last update.

完全数とは

小説「博士の愛した数式」で一般の人にも有名になった「完全数」ですが、その完全数を求めるプログラムです。
完全数とは、その数自身を除く約数の和が、その数自身と等しい自然数のことです。

例えば、28 の約数は、1,2,4,7,14ですが、この合計は、1+2+4+7+14 = 28 となりますので、28は完全数ということになります。

どうやって解くか

この問題を普通にプログラミングすると、約数を求め、その和がそれ自身の数と等しいかどうかを調べてゆくことになります。しかしこのやり方だと小さいほうから最初の4つまではすぐに求まりますが、5つ目、6つ目の完全数を求めようとすると、答えが出るまでかなりの時間待たされることになります。

そのためこのプログラムでは、

「完全数はメルセンヌ素数から導き出される」

という性質を利用することにしました。
2^n-1が素数(メルセンヌ素数)ならば、偶数の完全数は、2^(n-1)・(2^n-1) で求められることが証明されているそうです。

奇数の完全数はまだ発見されていません。奇数の完全数が存在しないことはまだ証明がされていないそうです。

C#のコード

PerfectNumber.cs
  public class PerfectNumber {
      public static IEnumerable<long> Take(int maxcount) {
          int count = 0;
          long n = 2;
          while (count < maxcount) {
              long mp = (long)Math.Pow(2, n) - 1;
              if (PrimeNumber.IsPrime(mp)) {
                  long pn = (long)(Math.Pow(2, n - 1) * mp);
                  count++;
                  yield return pn;
              }
              n++;
          }
      }
  }

PrimeNumber.IsPrime()は、「ミラー・ラビン素数判定法」による素数判定メソッドで示したメソッドをそのまま利用しています。

このクラスを使い、完全数を小さい順から8つ求めてみます。

public static void Main(string[] args) {
    var q = PerfectNumber.Take(8);
    foreach (var n in q) {
        Console.WriteLine(n);
    }
}

実行結果

結果です。


6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128

8番目までの完全数ならば、すぐに求まります。

しかし、9番目の完全数は、2658455991569831744654692615953842176 なので、long型では無理みたいです。

ところで、1の位が6か8なのは、単なる偶然なんでしょうか?
Webで調べたところ、見つかっている完全数の1の位はどれも、6か8みたいです。面白いですね。


この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。

5
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
gushwell
株式会社ジード / Microsoft MVP for Developer Technologies 2005-2020 / 著書『実戦で役立つ C#プログラミングのイディオム/定石&パターン』『新・標準プログラマーズライブラリ なるほどなっとく C#入門』『C#プログラミング入門―オブジェクト指向のプログラミング手法を基礎から解説』

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
5
Help us understand the problem. What is going on with this article?