Help us understand the problem. What is going on with this article?

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

More than 1 year has 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で公開したものを加筆・修正したものです。

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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした