Поиск совершенных чисел (оптимизация)

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

Answer 1

Используйте формулу

testperfect = 2.N-1.(2N. - 1)

Чтобы генерировать возможности, то проверьте, номер на самом деле идеально.

попробуйте это для некоторого числа сна

Answer 2

Сделайте идеальные номера? Нет. Смотри сюда. Отказ Конечно, они должны быть рассчитаны один раз, а затем сохранены. В вашем случае единственные результаты будут

6
28
496
8128

Следующий 33550336. За пределами вашего диапазона.

Answer 3

Просто очевидное от меня: вам не нужно проверять каждый делитель. Нет смысла в поисках делителей прошлых inputNo/2. Отказ Это сокращает половину расчетов, но это не порядка быстрее.

Answer 4

Один из способов решить такие вещи, как это включает в себя создание огромного массива в память о каждом номере, а затем выходить из них.

Answer 5

Если вы все еще ищете что-то, чтобы рассчитать идеальные номера. Это проходит через первые десять тысяч довольно быстро, но число 33 миллионов немного медленнее.

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

Для тех, кто заинтересован в подходе на основе 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;
}

Для простоты и ясности моя реализация для ISPRIME (), которая используется в пределах IsperfectNumber (), опущена.

Answer 7

Чтобы продолжить от ответа Чарльза Гордрента, есть очень быстрый способ проверить, является ли номер Mersenne AKA 2 ^ N - 1 Prime. Это называется Испытание Lucas-LehmerОсновной псевдокод, хотя (взятый с страницы 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