查找最多10000个可配对数字

#include<stdio.h>

int main()
{
    printf("|---------- PROGRAM FOR AMICABLE NUMBERS.----------|");
    int num1,num2,sum=0;
    for(num1=1; num1<=10000; num1++)
    {
        for(num2=1; num2<=10000; num2++)
            {
                if ((num1==sum_of_divisors(num2)) && (num2==sum_of_divisors(num1)) && num1!=num2)
                {
                    printf("\n%d\t\t%d", num1,num2);
                }
            }
    }
    return 0;
}

int sum_of_divisors(int n)
{
    int sum=0,i;
    for(i=1; i<n; i++)
    {
         if(n%i==0)
         {
              sum=sum+i;
         }         
    }   
    return sum;
}

#1 楼

    printf("|---------- PROGRAM FOR AMICABLE NUMBERS.----------|");

这种横幅消息使在管道中使用程序的输出变得更加困难。我建议删除它（用户已选择运行它；让他们知道他们在做什么！）。

    int num1,num2,sum=0;

sum的作用是什么？似乎没有使用。

    for(num1=1; num1<=10000; num1++)

10000的神奇价值从何而来？它应该是一个命名常量（或者更好，可以指定为命令行参数）。

        for(num2=1; num2<=10000; num2++)

我们真的需要考虑双向的每一对吗？我们可以简单地迭代num2 < num1（这也节省了以后的比较）。但是请参阅下面的内容，为什么根本不需要此循环。

                if ((num1==sum_of_divisors(num2))

sum_of_divisors()没有可见的原型-启用相关的编译器警告并提供原型（例如，通过将定义移至前面） main()）。

        for(num2=1; num2<=10000; num2++)
            {
                if ((num1==sum_of_divisors(num2))
                    && (num2==sum_of_divisors(num1))
                    && num1!=num2)

在内部循环中，sum_of_divisors(num1)是一个常数，因此我们可以将其保存在外部循环中，并进行第一个比较（以便将&&短路会然后仅评估一次sum_of_divisors(num2)）。然后观察到我们有一个循环来测试其索引是否等于特定值-这意味着我们用一个测试替换了内部循环：

    for (num1 = 1;  num1 <= 10000;  num1++) {
         num2 = sum_of_divisors(num1);
         if (num1 < num2 && sum_of_divisors(num2) == num1) {
             /* we found a pair */
         }
    }

那里的num2 < num1测试为我们节省了重新查找的时间对，我们已经见过。当然，num2 > num1也可以使用-我选择此版本，以便我们按照惯例从低到低的顺序打印每对。

                    printf("\n%d\t\t%d", num1,num2);

最好始终结束输出以换行符开头，而不是以换行符开头。这在可能发出错误或其他诊断信息的程序中效果更好，并且与行缓冲输出（例如交互式终端（换行符会导致刷新））配合使用时效果很好。

    for(i=1; i<n; i++) if(n%i==0) sum += i;

这是积累因子的一种非常低效的方法。您可以使用sum += i + n/i将其减小到范围（1，√n）（稍作调整以避免√n为正方形时重复计数n）；最好是生成所有主要因子，然后使用它们来生成复合因子。

进行了上述改进之后，我发现运行时间低于我的测量阈值。将限制增加到一百万可以使运行时间大约为2秒-这可能是可以接受的；如果不是这样，则问题可以很好地并行化（除了输出结果之外）。

修改版本

#include <stdio.h>

#if USE_LONG_TYPE
typedef unsigned long Number;
#define FMT "%lu"
#else
typedef unsigned int Number;
#define FMT "%u"
#endif

static const Number MAX_VALUE = 1000000;


Number sum_of_factors(Number n)
{
    Number sum = 1;
    Number i = 2;
    for (;  i < n/i;  ++i) {
        if (n/i*i == n) {
            sum += i + n/i;
        }
    }
    if (i*i == n)
        sum += i; /* add square root only once */
    return sum;
}

int main()
{
    //#pragma omp parallel for
    for (Number num1 = 1;  num1 <= MAX_VALUE;  ++num1) {
        Number num2 = sum_of_factors(num1);
        if (num2 > num1 && num1 == sum_of_factors(num2)) {
            printf(FMT "\t\t" FMT "\n", num1, num2);
        }
    }
}

#2 楼

    for(num1=1; num1<=10000; num1++)
    {
        for(num2=1; num2<=10000; num2++)
            {
                if (... && (num2==sum_of_divisors(num1)) && ...)

这里有一个明显的优化，它将使您的速度提高大约10000倍...

int sum_of_divisors(int n)
{
    int sum=0,i;
    for(i=1; i<n; i++)
    {
         if(n%i==0)
         {
              sum=sum+i;

这不是最快的计算方法。

优化1：仅循环至i*i <= n并使用以下事实：如果n / i = j则n / j = i。

优化2：给定素数分解，除数之和的公式是什么？优化3：您实际上不想要一个数的除数之和，但所有的除数不超过N。如何有效地调整Eratosthenes的筛子，以有效计算N以下所有数字的除数之和？

#3 楼

请尝试以下操作（速度更快）：

int num, num2, num3;
for (num1 = 1; num1<=10000; num1++)
{
    num2 = sum_of_divisors(num1);
    if (num1 < num2)    /* at least one of any amicable pair is larger */
    {
        num3 = sum_of_divisors(num2);
        if (num3 == num1)    /* FOUND AN AMICABLE PAIR! */
            ... (record the pair) ...
    }
}

#4 楼

for(num1=1; num1<=10000; num1++)
{
    for(num2=1; num2<=10000; num2++)
        {
            if ((num1==sum_of_divisors(num2)) && (num2==sum_of_divisors(num1)) && num1!=num2)

要添加一个小注释，其他2个答案未提及：

您调用sum_of_divisors（）的次数约为应有的20000倍。

您使用相同的输入值多次调用它，这是一个相当昂贵的函数。

如果您一次对数字1到10000计算sum_of_divisors（），就在程序开始时，将输出存储在数组中，并在需要该值时查看它，那么您就不会最终需要重复进行相同的工作〜10,000x次，而您可以只做一次。

#5 楼

要考虑的一件事是sum_of_divisors函数。

它是一个纯函数，意味着其返回值仅取决于输入参数i。

此外，它被称为100,000,000次，但值只有1到1,000,000。

memoization已经成熟。这基本上意味着，在调用函数时，将以输入参数为键来缓存返回值。随后具有相同输入参数的调用仅返回缓存的值。

因此，

int sum_of_divisors(int n)
{
    int sum=0,i;
    for(i=1; i<n; i++)
    {
         if(n%i==0)
         {
              sum=sum+i;
         }         
    }   
    return sum;
}

成为

int sums[1000000];
int sum_of_divisors(int n)
{
    if(sums[n]) {
       return sums[n];
    }
    int sum=0,i;
    for(i=1; i<n; i++)
    {
         if(n%i==0)
         {
              sum=sum+i;
         }         
    }   
    sums[n] = sum;
    return sum;
}

#6 楼

我认为这是解决您问题的最佳方法之一。它的工作时间约为1秒钟，并找到1到2000万之间的所有对。
首先，我们需要使用以下方法计算每个数字的最小除数：Eratosthenes筛。
然后我们使用sigma（ n）-n的所有除数之和是乘法函数。对于每个数字，我们知道它的最小除数-p。找出我可被p ^ k整除的最大k。现在，sigma（i）是sigma（p ^ k）* sigma（i / p ^ k）
现在，我们可以计算每个数字的适当除数之和。 sum_proper [i] = sigma [i]-i。
最后，让我们遍历i并检查sigma [sigma [i]] = i并打印答案。
代码

#include <stdio.h>

const int N = 20000000;
const int CNT_PRIMES = N; // upper bound on number of primes within range from 1 to N

int main()
{
    int smallest_divisor[N];
    int sigma[N];
    int sum_proper[N];
    int primes[CNT_PRIMES];
    int curcnt = 0;
    for (int i = 2; i < N; ++i)
        smallest_divisor[i] = i;
    for (int i = 2; i < N; ++i)
    {
        if (smallest_divisor[i] == i)
            primes[curcnt++] = i;
        for (int j = 0; j < curcnt && primes[j] <= smallest_divisor[i] && primes[j] * i < N; ++j)
            smallest_divisor[primes[j] * i] = primes[j];
    }
    sigma[1] = 1;
    for (int i = 2; i < N; ++i)
    {
        int cur = i;
        int p = smallest_divisor[i];
        int k = 0;
        while (cur % p == 0)
            cur /= p, ++k;
        int pk = i / cur;
        sigma[i] = (pk * p - 1) / (p - 1); // sigma(p^k) = 1 + p + ... + p^k = (p^(k+1) - 1) / (p - 1)
        sigma[i] *= sigma[cur];
        sum_proper[i] = sigma[i] - i;
    }
    for (int i = 2; i < N; ++i)
    {
        int j = sum_proper[i];
        if (j < N && j > i && sum_proper[j] == i)
            printf("%d\t\t%d\n", i, j);
    }
}

Idone演示

#7 楼

这实际上是Euler项目的问题21。

如果您想要纯粹的性能，就完全摆脱分歧。

我对C的了解不够，无法实际审查代码，但是几年前我写了一个针对Java的有效解决方案，并希望共享它。该算法非常简单，只需要对除数的思考方式进行一些更改即可。您会看到，我基本上只使用加法（一次除外，用于……加倍）。

 // Note: this is Java, not C
public static int projectEuler21(final int limit) {

  int[] sumOfDivisors = new int[limit];
  int sum = 0;

  // For each number below the limit
  for (int number = 1; number < limit; number++) {

    // Add it as divisor to each of its multiples
    for (int multiple = number * 2; multiple < limit; multiple += number) {
      sumOfDivisors[multiple] += number;
    }

    // sum both number and sumOfDivisors[number] if they're amicable, but only if number is the larger of the pair
    if (sumOfDivisors[number] < number && number == sumOfDivisors[sumOfDivisors[number]]) {
      sum += number + sumOfDivisors[number];
    }
  }
  return sum;
}
 

上面的代码以大约2或3毫秒的速度运行，因此表现出色。如果将限制更改为20,000,000，则会在5到6秒之间运行。