Пары дружных номеров

Question

У меня есть задача найти пары дружных чисел, и я уже решил ее.Мое решение неэффективно, поэтому, пожалуйста, помогите мне ускорить мой алгоритм.

Достижимые числа - это два разных числа, связанных так, что сумма правильных делителей каждого равна другому числу.Наименьшая пара дружных чисел - (220, 284).Они дружны, потому что правильными делителями 220 являются 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, из которых сумма равна 284;а правильными делителями 284 являются 1, 2, 4, 71 и 142, из которых сумма равна 220.

Задача: два long числа и найти первые дружные числа между ними.Пусть s (n) будет суммой правильных делителей числа n:

Например:

s(10) = 1 + 2 + 5 = 8
s(11) = 1
s(12) = 1 + 2 + 3 + 4 + 6 = 16

Если s(firstlong) == s(secondLong), то они являются дружными числами

Мой код:

public static IEnumerable<long> Ranger(long length) {
  for (long i = 1; i <= length; i++) {
    yield return i;
  }
}

public static IEnumerable<long> GetDivisors(long num) {
  return from a in Ranger(num/2)
    where num % a == 0
    select a;
}

public static string FindAmicable(long start, long limit) {
  long numberN = 0;
  long numberM = 0;

  for (long n = start; n <= limit; n++) {
    long sumN = GetDivisors(n).Sum();      
    long m = sumN;

    long sumM = GetDivisors(m).Sum();

    if (n == sumM ) {
      numberN = n;      
      numberM = m;
      break;
    }
  }

  return $"First amicable numbers: {numberN} and {numberM}";
}

Answer 1

Существует простая формула, дающая сумму делителей числа, знающего его простое разложение:

 let x = p1^a1 * ... * pn^an, where pi is a prime for all i
 sum of divisors = (1+p1+...+p1^a1) * ... (1+pn+...+pn^an)
                 = (1-p1^(a1+1))/(1-p1) * ... ((1-pn^(an+1))/(1-pn)

Чтобы выполнить простое разложение, вы должны вычислить все простые числа до квадратного корня от максимального значения в вашем диапазоне поиска. Это легко сделать, используя сито Эратостен.

Answer 2

Я обычно не пишу на C #, поэтому вместо того, чтобы наткнуться на некогерентные спагетти на C #, я опишу улучшение в C # -madeup-psuedo-code.

Проблема, похоже, в вашем GetDivisors функция.Это линейное O(n) время по отношению к каждому делителю n, когда оно может быть O(sqrt(n)).Хитрость заключается в том, чтобы разделить только до квадратного корня и вывести остальные факторы из этого.

GetDivisors(num) {
    // same as before, but up to sqrt(num), plus a bit for floating point error
    yield return a     in Ranger((long)sqrt(num + 0.5)) where num % a == 0

    if ((long)sqrt(num + 0.5) ** 2 == num) { // perfect square, exists
        num -= 1 // don't count it twice
    }

    // repeat, but return the "other half"-  num / a  instead of  a
    yield return num/a in Ranger((long)sqrt(num + 0.5)) where num % a == 0
}

Это уменьшит сложность этой части с O(n) до O(sqrt(n)), что должнообеспечить заметное ускорение.