c - 友好数算法的优化建议

Question

我在寻找友好数字对的算法中遇到了一个时间复杂度很高的问题。尽管输入的上限为 10000，但找到所有对需要 3 分钟。

如何优化下面的代码？

#include <stdio.h>

int sumofdiv(int);
void amicable_nums(int);

int main()
{
  int limit;
  printf("Enter the limit to check amicable numbers: ");
  scanf("%d", &limit);
  amicable_nums(limit);
  return 0;
}

void amicable_nums(int limit)
{
  int num1, num2, sum1, sum2;
  for(num1=220; num1<limit; num1++)
  {
    if ((num1%2 != 0) && (num1%3 != 0) && (num1%5 != 0))//prime number detection (odd num > 220, so number 2, for example, that is prime doesn't count), prime number can't be amicable
    {
      continue;
    }
    for (num2 = num1+1; num2<limit; num2++)
    {
      if ((num1%2==0 && num2%2 != 0) || (num1%2 != 0 && num2%2 == 0))//only both odd or even numbers can be amicable
      {
        continue;
      }
      if ((num2%2 != 0) && (num2%3 != 0) && (num2%5 != 0))//the same prime number detection as before
      {
        continue;
      }
      sum1 = sumofdiv(num1);
      if (sum1 != num2)//if the sum of proper divisors of the first number is NOT equal to the second number, there is no reason to check the sum of proper divisors of the second number
      {
        continue;
      }
      sum2 = sumofdiv(num2);
      if (sum1 == num2 && sum2 == num1 && num1 != num2)
      {
        printf("(%d, %d)\n", num1, num2);
      }
    }
  }
}

int sumofdiv(int num)
{
  int div, sum = 0, even_limit = num/2, odd_limit = num/3;
  if (num%2 == 0)
  {
    for (div=1; div<even_limit; div++)
    {
      if ((num%div) == 0)
      {
        sum += div;
      }
    }
    sum += even_limit;
  }
  else
  {
    for (div=1; div<odd_limit; div+=2)//odd number can't be divided by even number
    {
      if ((num%div) == 0)
      {
        sum += div;
      }
    }
    sum += odd_limit;
  }
  return sum;
}

P.S.:代码中有几条语句的注释。 我尽量避免使用素数，避免计算很多默认情况下不友好的数字；然而，计算仍然很慢。我还在嵌套的 for 循环中对 num1 或/和 num2 进行了更多跳转，但它输出的对数比必须的要少。

Answer 1

您的算法的时间复杂度大于 O(N³) 因为对于每个 num1，您尝试了 的大多数值num2 和sumofdiv() 的计算也具有线性复杂度。

您可以通过每次迭代只测试一个值来大大降低这种复杂性:如果 sumofdiv(sumofdiv(num1)) == num1)，您就有一对友好的数字。

这是一个简单但有效的实现:

void amicable_nums(int limit) {
    int num1, num2;
    for (num1 = 1; num1 < limit; num1++) {
        num2 = sumofdiv(num1);
        if (num2 > num1 && sumofdiv(num2) == num1) {
            printf("(%d, %d)\n", num1, num2);
        }
    }
}

在我的系统上，扫描到 10000 的时间从 71 秒减少到不到 100 毫秒。还要注意代码的简单性和通用性:没有测试特殊情况。

您的函数 sumofdiv() 也可以简化和加速，提供另一个 10 倍的速度提升(对于 10000)，最终复杂度略高于 O(N^1.5 )。

这是改进后的代码:

#include <stdio.h>
#include <stdlib.h>

int sumofdiv(int num) {
    int div, sum = 1;

    for (div = 2; div * div <= num; div++) {
        if (num % div == 0) {
            int quo = num / div;
            sum += div;
            if (quo != div)
                sum += quo;
        }
    }
    return sum;
}

void amicable_nums(int limit) {
    int num1, num2;
    for (num1 = 1; num1 < limit; num1++) {
        num2 = sumofdiv(num1);
        if (num2 > num1 && sumofdiv(num2) == num1) {
            printf("(%d, %d)\n", num1, num2);
        }
    }
}

int main(int argc, char *argv[]) {
    int limit;
    if (argc > 1) {
        /* this is optional, for testing purposes */
        limit = strtol(argv[1], NULL, 0);
    } else {
        printf("Enter the limit to check amicable numbers: ");
        scanf("%d", &limit);
    }
    amicable_nums(limit);
    return 0;
}

输出:

~/dev/stackoverflow > time ./amicable 10000
(220, 284)
(1184, 1210)
(2620, 2924)
(5020, 5564)
(6232, 6368)

real    0m0.009s
user    0m0.007s
sys     0m0.001s

进一步的测试在 122 毫秒内产生了 13 对高达 100000，在 3.6 秒内产生了 42 对高达 1000000，在 2 分钟内产生了 108 对高达 10000000。