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

Я кодировал программу в C# для нахождения совершенных чисел в определенном диапазоне как часть проблемы программирования. Однако я понял, что это очень медленно при вычислении совершенных чисел вверх 10 000. Есть ли какие-либо методы оптимизации, которые существуют для нахождения совершенных чисел? Мой код следующие:

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);
  }
 }
} 
5
задан false 18 June 2014 в 12:52
поделиться

4 ответа

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

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

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

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

3
ответ дан 14 December 2019 в 13:30
поделиться

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

0
ответ дан 14 December 2019 в 13:30
поделиться

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

6
28
496
8128

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

2
ответ дан 14 December 2019 в 13:30
поделиться

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

1
ответ дан 14 December 2019 в 13:30
поделиться
Другие вопросы по тегам:

Похожие вопросы: