完璧な数字を見つける（最適化）

StackOverflow https://stackoverflow.com/questions/2651573

質問

プログラミングチャレンジの一環として、特定の範囲内で完全な数字を見つけるように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);
  }
 }
}
役に立ちましたか？

解決

式を使用します

testPerfect = 2n-1(2n - 1)

可能性を生成するには、数字が実際に完璧であるまで確認します。

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

他のヒント

完璧な数字は変わりますか？いいえ。 ここを見て. 。確かに、それらは一度計算してから保存する必要があります。あなたの場合、唯一の結果は次のとおりです

6
28
496
8128

次は33550336です。範囲外。

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

このようなことを解決する1つの方法には、すべての数を記憶して膨大な配列を構築し、数字を取り除くことが含まれます。

まだ完璧な数字を計算するための何かを探している場合。これは、最初の1万人をかなり速く通過しますが、3300万の数は少し遅いです。

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;
}
}

LINQベースのアプローチに興味がある人にとっては、次の方法は、発信者が整数値を提供するかどうかを判断するのに非常にうまく機能し、効率的に機能しました。

bool IsPerfectNumber(int value)
{
    var isPerfect = false;

    int maxCheck = Convert.ToInt32(Math.Sqrt(value));
    int[] possibleDivisors = Enumerable.Range(1, maxCheck).ToArray();
    int[] properDivisors = possibleDivisors.Where(d => (value % d == 0)).Select(d => d).ToArray();
    int divisorsSum = properDivisors.Sum();

    if (IsPrime(divisorsSum))
    {
        int lastDivisor = properDivisors.Last();
        isPerfect = (value == (lastDivisor * divisorsSum));
    }

    return isPerfect;
}

簡単にし、明確にするために、isperfectnumber（）内で使用されるisprime（）の実装は省略されています。

チャールズ・ガージェントの答えを継続するには、メルセンヌ番号別名2^n -1がプライムかどうかを確認する非常に迅速な方法があります。それはと呼ばれます Lucas-Lehmerテストしかし、基本的な擬似コード（ウィキペディアページから取られた）は次のとおりです。

// Determine if Mp = 2p − 1 is prime for p > 2
Lucas–Lehmer(p)
    var s = 4
    var M = 2p − 1
    repeat p − 2 times:
        s = ((s × s) − 2) mod M
    if s == 0 return PRIME else return COMPOSITE
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top