Encontrar números perfectos (optimización)

Question

codifiqué un programa en C # para encontrar números perfectos dentro de un cierto rango, como parte de un desafío de programación. Sin embargo, me di cuenta que es muy lento cuando se calcula números perfectos más de 10000. ¿Existen métodos de optimización que existen para encontrar números perfectos? Mi código es el siguiente:

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

Usar la fórmula

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

para generar posibilidades entonces comprobado si el número es de hecho perfecto.

probar esto durante algún libro de cabecera

Answer 2

¿Se modifican los números perfectos? Nº Mira aquí . Sin duda, deben ser calculados una vez y luego almacenados. En su caso, los únicos resultados serán

6
28
496
8128

El siguiente es 33550336. fuera de su rango.

Answer 3

Sólo la más obvia de mí: no es necesario comprobar cada divisor. No tiene sentido buscar divisores últimos inputNo/2. Que reduce la mitad de los cálculos, pero esto no es un orden de magnitud más rápido.

Answer 4

Una manera de resolver este tipo de cosas implica la construcción de una enorme variedad en la memoria de cada número, y luego los números tachando.

Answer 5

si su todavía en busca de algo para calcular los números perfectos. esto pasa por el primer diez mil bastante rápido, pero los 33 millones el número es un poco más lento.

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

Para cualquier persona interesada en un enfoque basado en LINQ, el siguiente método funcionó bastante bien y eficientemente para mí en la determinación de si o no un valor entero que llama suministrado es un número perfecto.

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

Por simplicidad y claridad, se ha omitido mi aplicación para IsPrime (), que se utiliza en IsPerfectNumber (),.

Answer 7

Para continuar de la respuesta de Charles Gargent hay una manera muy rápida de comprobar si un número de Mersenne alias 2 ^ n - 1 es primo. Se llama la Lucas-Lehmer prueba El pseudocódigo básico, aunque (tomado de la página de Wikipedia) es:

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