Trovare i numeri perfetti (ottimizzazione)

Question

ho codificato un programma in C # per trovare i numeri perfetti entro un certo intervallo, come parte di una sfida di programmazione. Tuttavia, mi sono reso conto che è molto lento nel calcolo numeri perfetti verso l'alto di 10000. Ci sono dei metodi di ottimizzazione che esistono per la ricerca di numeri perfetti? Il mio codice è il seguente:

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

Usa la formula

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

per generare possiblities quindi controllare montone il numero è in realtà perfetta.

provare questo per una certa lettura di andare a dormire

Answer 2

Do numeri perfetti cambiamento? No. Guardate qui . Sicuramente, essi dovrebbero essere calcolati una sola volta e quindi memorizzati. Nel tuo caso, gli unici risultati saranno

6
28
496
8128

Il prossimo è 33550336. Al di fuori la vostra gamma.

Answer 3

Proprio l'ovvia da me: non c'è bisogno di controllare ogni divisore. Nessun punto in cerca di divisori ultimi inputNo/2. Che taglia a metà dei calcoli, ma non si tratta di un ordine di grandezza più veloce.

Answer 4

Un modo per risolvere le cose in questo modo comporta la costruzione di una matrice enorme in memoria di ogni numero, e poi attraversando numeri su.

Answer 5

Se la vostra ancora alla ricerca di qualcosa di calcolare numeri perfetti. questo passa attraverso il primo diecimila piuttosto veloce, ma il numero di 33 milioni è un po 'più 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

Per chiunque sia interessato a un approccio basato LINQ, il seguente metodo ha funzionato abbastanza bene e in modo efficiente per me nel determinare se un valore intero chiamante fornito è un numero perfetto.

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

Per semplicità e chiarezza, mia implementazione per isPrime (), che viene utilizzato all'interno IsPerfectNumber (), viene omesso.

Answer 7

Per continuare dalla risposta di Charles Gargent c'è un modo molto rapido per verificare se un numero di Mersenne anche noto come 2 ^ n - 1 è primo. Si chiama Lucas-Lehmer test di Il pseudocodice base però (preso dalla pagina di Wikipedia) è:

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