2015年01月21日

C#で10000以下のダブル完全数をすべて求める

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その64

■問題 (出題者:にしお さん)
「完全数」とは、自分以外の約数の和が自分自身と等しいような整数のことです。
ここで「自分以外の約数の和が自分自身の2倍と等しいような整数」を「ダブル完全数」と呼ぶことにします。10000以下のダブル完全数をすべて求めるコードを書いてください。

最初に書いたコード。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
           
            for (long i = 0; i <= 10000; i++)
                if (IsDoublePerfect(i)) 
                    Console.WriteLine(i);
                
            Console.WriteLine("end");
            Console.ReadLine();
        }

        static bool IsDoublePerfect(long n) {
            long r = 1;
            for (int i = 2; i <= n / 2; i++) {
                if (n % i == 0)
                    r += i;
            }
            return (n * 2 == r);
        }
    }
}


10000までのダブル完全数は、120, 672 の2つでした。
では、672の次のダブル完全数はいくつかな、と思って、 10000 を 1000000 までにしてみたら遅い。
いつまで待っても終わりません。 とんでもなく遅いです。いくらなんでも遅すぎます(T T)

ということで、ちょっと改良したコード。

static bool IsDoublePerfect(long n) {
    long r = 1;
    long limit = (long)Math.Sqrt(n);
    for (int i = 2; i <= limit; i++) {
        if (n % i == 0)
            r += i + (n / i);
    }
    return (n * 2 == r);
}

例えば、18 の約数を調べるとすると、2で割り切れたら、その商である 9も約数であることは明白なので、
r += i + (n / i);

で、2と9を加えています。当
然、約数かどうかは、(long)Math.Sqrt(n) まで調べれば 良いことになります。
たったこれだけで、随分と速くなりました。
3つ目のダブル完全数が知りたい方は、実際に動かしてみてください。
 


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52403787