c# - 友好数字对

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

我通常不编写 C#，因此我不会偶然发现一些不连贯的 C# 意大利面条，而是描述 C#-madeup-psuedo-code 的改进。

问题似乎出在您的 GetDivisors 函数中。这是关于每个除数 n 的线性 O(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))，这应该会提供明显的加速。