c++ - 使用函数 C++ 查找完全数

Question

我在处理程序中的特定问题时遇到了问题。

首先，我需要确定一个数字是否完美。使用一个名为: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;
    }

}

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

Answer 1

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

要解决这个问题，您首先要根据上面的公式计算一个完全数的候选者。您可以使用 math.h 提供的 pow 函数，即使它是为浮点使用而设计的，或者您也可以简单地创建自己的循环遍历的值candidate p 将 p 自身乘以最终结果数组所需的次数，例如类似于以下内容:

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

    return tmp;
}

(注意:应添加溢出检查以防止无符号溢出——使用 unsigned 4 字节类型的完全数可能会发生超出 5 的情况^第)

该算法的其余部分非常简单，您只需循环从 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 header ，为要生成的最大完美数数和除数数组声明几个常量。总而言之，您可以执行类似于以下操作的操作:

#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

所有前五个完全数的计算时间都不到十分之二秒，系统时间仅为千分之八秒。

算法改变了世界。