0

我在解决程序中的特定问题时遇到了麻烦。

首先，我需要确定一个数字是否完美。使用我在这里制作的名为 bool isPerfect(int n) 的函数：

bool isPerfect(int n) {

    sum = 0;

    for (int i = 1; i < n; i++) {

        if (n % i == 0)
            sum += i;
    }

    if (sum == n) {
        return true;
    }
    else {
        return false;
    }

}

我面临的问题是第二步。我需要创建生成许多整数进行测试的代码。然后测试这些整数，直到我找到并打印出其中五个完美的整数。我写的意大利面条代码最终花费了太长时间来计算第五个完美数字。我可以采取哪些步骤来减少测试如此大量数字所需的时间？就像我可以制定一个规则来跳过数字以测试我知道我不需要的？很感谢任何形式的帮助。

4

1 回答 1

1

Euclid 证明了2 p−1 (2 p − 1)是一个偶完美数，只要2p − 1是素数。请参阅：Wikipedia - Even perfect numbers这提供了一个框架，用于在几乎微不足道的少量计算中生成所有候选完美数。这里的目标是找到前五个完美数字。幸运的是，前五个很容易适合 4 字节unsigned数据类型，并且可以在比键入 [Ctrl+C] 所需的时间更短的时间内计算出来。

为了解决这个问题，你首先从上面的公式中计算出一个完美数字的候选者。即使它是为浮点使用而设计的，您也可以使用pow提供的函数，或者您可以简单地创建自己的函数，循环遍历候选值的值，将其自身乘以最终结果的数组，例如类似于以下内容：math.hpp

unsigned upow (unsigned v, unsigned n)  /* unsigned pow() */
{
    unsigned tmp = 1;
    if (n == 0)
        return 1;
    while (n--)
        tmp *= v;

    return tmp;
}

（注意：应添加溢出检查以防止无符号溢出——对于超过 5 thunsigned的 Perfect Numbers 使用 4 字节类型可能会发生这种情况）

算法的其余部分相当简单，您只需将候选中的数字从1到candidate / 2（包括）循环，以确保找到所有因子，求和并存储在包含各个除数的数组中以供以后显示。

该方法的一个简短示例如下所示：

    unsigned sum = 0, i, j, p, pn, pncount = 0;     /* variable declarations   */
    for (p = 2; p < 32; p++) {                      /* generate candidate from */
        unsigned divisors[NELEM] = {0}, n = 0;      /* divisors array and ndx */
        pn = upow (2, p - 1) * (upow (2, p) - 1);   /* 2^(n - 1) * (2^n - 1)  */
        for (i = 1; i <= pn / 2; i++) {             /* find divisors & sum */
            if (pn % i == 0) {
                sum += i;
                divisors[n++] = i;                  /* store divisor to array */
            }
            if (n == NELEM) {                       /* protect array bound */
                fprintf (stderr, "error: f full.\n");
                return 1;
            }
        }
        if (sum == pn) {    /* test whether candidate is Perfect Number */
            printf ("Perfect number: %10u :", pn);
            for (j = 0; j < n; j++)                /* output divisors */
                printf (j ? ", %u" : " %u", divisors[j]);
            putchar ('\n');
            if (++pncount == MAXPN)                 /* check against limit */ 
                break;
        }
        sum = 0;    /* reset sum for next iterations */
    }

剩下的就是添加stdio.h标题，为我们要生成的最大完美数和除数数组声明几个常量。总而言之，您可以执行类似于以下的操作：

#include <stdio.h>

#define MAXPN    5  /* const - max perfect numbers to find */
#define NELEM 4096  /* const - elements in divisors array */

unsigned upow (unsigned v, unsigned n)  /* unsigned pow() */
{
    unsigned tmp = 1;
    if (n == 0)
        return 1;
    while (n--)
        tmp *= v;

    return tmp;
}

int main (void) {

    unsigned sum = 0, i, j, p, pn, pncount = 0;     /* variable declarations   */
    for (p = 2; p < 32; p++) {                      /* generate candidate from */
        unsigned divisors[NELEM] = {0}, n = 0;      /* divisors array and ndx */
        pn = upow (2, p - 1) * (upow (2, p) - 1);   /* 2^(n - 1) * (2^n - 1)  */
        for (i = 1; i <= pn / 2; i++) {             /* find divisors & sum */
            if (pn % i == 0) {
                sum += i;
                divisors[n++] = i;                  /* store divisor to array */
            }
            if (n == NELEM) {                       /* protect array bound */
                fprintf (stderr, "error: f full.\n");
                return 1;
            }
        }
        if (sum == pn) {    /* test whether candidate is Perfect Number */
            printf ("Perfect number: %10u :", pn);
            for (j = 0; j < n; j++)                /* output divisors */
                printf (j ? ", %u" : " %u", divisors[j]);
            putchar ('\n');
            if (++pncount == MAXPN)                 /* check against limit */ 
                break;
        }
        sum = 0;    /* reset sum for next iterations */
    }
}

性能是关键。正如您所发现的那样，由于蛮力方法需要数万亿次计算迭代所有可能的组合和可能的完美数，即使在快速机器上，您也可能有时间在第 5 种情况下完成短暂的假期.

测试输出表明算法对于前五个完美数字是可靠的，例如

*示例使用/输出**

$ ./bin/perfnumber
Perfect number:          6 : 1, 2, 3
Perfect number:         28 : 1, 2, 4, 7, 14
Perfect number:        496 : 1, 2, 4, 8, 16, 31, 62, 124, 248
Perfect number:       8128 : 1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 
                             1016, 2032, 4064
Perfect number:   33550336 : 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 
                             1024, 2048, 4096, 8191, 16382, 32764, 65528, 
                             131056, 262112, 524224, 1048448, 2096896, 
                             4193792, 8387584, 16775168

（注意：组成的独立除数的输出sum被整齐地包装以避免在这里滚动SO，通常它们只是在完美数字后面按顺序给出）。

至于代码的时间，只需一个简单的调用就可以time对所需的计算时间进行相对比较，例如

大概的运行时间

$ time ./bin/perfnumber
  <snip output>

real    0m0.146s
user    0m0.139s
sys     0m0.008s

所有前五个完美数的计算都在不到十分之二秒的时间内，只需要千分之八秒的系统时间。

该算法使世界变得与众不同。

于 2018-02-17T12:24:08.353 回答