c# - 完全数を見つける (最適化)

Question

プログラミングチャレンジの一環として、特定の範囲内で完全数を見つけるプログラムを C# でコーディングしました。ただし、10000 以上の完全数を計算すると非常に遅いことに気付きました。完全数を見つけるための最適化の方法はありますか? 私のコードは次のとおりです。

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

namespace ConsoleTest
{
 class Program
 {
  public static List<int> FindDivisors(int inputNo)
  {
   List<int> Divisors = new List<int>();
   for (int i = 1; i<inputNo; i++)
   {
    if (inputNo%i==0)
     Divisors.Add(i);
   }
   return Divisors;
  }

  public static void Main(string[] args)
  { 
   const int limit = 100000;

   List<int> PerfectNumbers = new List<int>();
   List<int> Divisors=new List<int>();
   for (int i=1; i<limit; i++)
   {
    Divisors = FindDivisors(i);
    if (i==Divisors.Sum())
     PerfectNumbers.Add(i);
   }

   Console.Write("Output =");

   for (int i=0; i<PerfectNumbers.Count; i++)
   {
    Console.Write(" {0} ",PerfectNumbers[i]);
   }

   Console.Write("\n\n\nPress any key to continue . . . ");
   Console.ReadKey(true);
  }
 }
}

score 4 · Accepted Answer

式を使用する

testPerfect = 2 ^n-1（2 ⁿ -1）

可能性を生成し、その数が実際に完全であるかどうかを確認します。

就寝前の読書のためにこれを試してみてください

score 2 · Accepted Answer

完全数は変化しますか？いいえ、ここを見てください。確かに、一度計算してから保存する必要があります。あなたの場合、唯一の結果は

次は 33550336 です。範囲外です。

score 1 · Accepted Answer

私からの明白な 1 つ: すべての除数をチェックする必要はありません。過去の約数を探しても意味がありませんinputNo/2。これにより、計算の半分が削減されますが、これは桁違いに高速ではありません。

score 0 · Accepted Answer

このような問題を解決する1つの方法は、すべての数値のメモリに巨大な配列を作成してから、数値を消すことです。

score 0 · Accepted Answer

完全数を計算する何かをまだ探しているなら。これは最初の 10,000 をかなり速く通過しますが、3,300 万の数は少し遅くなります。

public class Perfect {
private static Perfect INSTANCE = new Perfect();

public static Perfect getInstance() {
    return INSTANCE;
}

/**
 * the method that determines if a number is perfect;
 * 
 * @param n
 * @return
 */
public boolean isPerfect(long n) {
    long i = 0;
    long value = 0;
    while(++i<n){
        value = (0 == n%i?value+i:value);
    }
    return n==value;
}
}

c# - 完全数を見つける (最適化)

7 に答える 7

Related

Reference