Нахождение идеальных чисел (оптимизация)

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<sup>n-1</sup>(2<sup>n</sup> - 1)

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

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

Answer 2

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

6
28
496
8128

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

Answer 3

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

Answer 4

Чтобы продолжить ответ Чарльза Гаргента, есть очень быстрый способ проверить, простое ли число Мерсенна aka 2 ^ n - 1.Он называется тест Лукаса-Лемера Основной псевдокод (взятый из страницы Википедии):

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

Answer 5

Для всех, кто интересуется подходом, основанным на 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 6

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

Answer 7

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