Я кодировал программу в 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);
}
}
}
Используйте формула
testPerfect = 2n-1(2n - 1)
, чтобы сгенерировать возможности, а затем проверить, действительно ли число идеально.
Один из способов решения подобных задач заключается в создании огромного массива в памяти для каждого числа и последующем вычеркивании чисел.
Меняются ли идеальные числа? № Смотрите здесь . Разумеется, их следует рассчитать один раз, а затем сохранить. В вашем случае единственными результатами будут
6
28
496
8128
Следующим будет 33550336. За пределами вашего диапазона.
Просто очевидное от меня: вам не нужно проверять каждый делитель. Нет смысла искать делители после inputNo / 2
. Это сокращает половину вычислений, но не на порядок быстрее.