Trouver les nombres parfaits (optimisation)

Question

Je codé un programme en C # pour trouver les nombres parfaits dans une certaine gamme dans le cadre d'un défi de programmation. Cependant, je l'ai réalisé est très lent lors du calcul de nombres parfaits vers le haut de 10000. Existe-t-il des méthodes d'optimisation qui existent pour trouver les nombres parfaits? Mon code est le suivant:

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

Answer 1

Utiliser la formule

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

pour générer possiblities alors le nombre wether vérifier est en fait parfait.

essayer cela pour une lecture de l'heure du coucher

Answer 2

Do chiffres changent de parfaits? Non Regardez ici . Certes, ils doivent être calculées une fois, puis stockés. Dans votre cas, les seuls résultats seront

6
28
496
8128

Le prochain est 33550336. En dehors de votre gamme.

Answer 3

Juste une évidence de moi: vous n'avez pas besoin de vérifier chaque diviseur. Aucun point recherche inputNo/2 passé diviseurs. Cela permet de réduire la moitié vers le bas des calculs, mais ce n'est pas un ordre de grandeur plus rapide.

Answer 4

Une façon de résoudre les choses comme cela implique la construction d'un grand éventail dans la mémoire de chaque numéro, puis traverser les numéros sur.

Answer 5

si vous cherchez encore quelque chose à calculer les nombres parfaits. cela va à travers les dix premiers mille assez rapide, mais le nombre de 33 millions est un peu plus lent.

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

Answer 6

Pour toute personne intéressée par une approche basée sur LINQ, la méthode suivante fonctionnait très bien et efficace pour moi pour déterminer si oui ou non une valeur entière fourni de l'appelant est un nombre parfait.

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

Par souci de simplicité et de clarté, ma mise en œuvre pour ISPRIME (), qui est utilisé dans IsPerfectNumber (), est omis.

Answer 7

Pour continuer de la réponse de Charles Gargent il y a un moyen très rapide pour vérifier si un numéro Mersenne 2 ^ n a.k.a. - 1 est premier. Il est appelé test de Lucas-Lehmer Le pseudo-code de base que (extrait de la page Wikipedia) est:

// 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