Finding perfect number using functions C++

Question

I am having trouble approaching a specific problem in my program.

First, I needed to determine whether or not a number is perfect. Using a function called: bool isPerfect(int n) which I've made here:

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;
    }

}

The problem that I'm facing is the second step. That I need to create code that generates many integers for testing. Then test these integers until I've found and printed five of them that are perfect. The spaghetti code I wrote ended up taking too long to calculate the 5th perfect number. What steps could I take to reduce the amount of time that I need to test such large numbers? Like a rule that I could put in place to skip numbers to test that I know I don't need to? Any help is very much appreciated.

Answer 1

Euclid proved that 2^p−1(2^p − 1) is an even perfect number whenever 2p − 1 is prime. See: Wikipedia - Even perfect numbers This provides a framework for generating all candidates for perfect numbers in an almost trivially small set of computations. Here the goal is the find the first five Perfect Numbers. Luckily, the first five will easily fit in a 4-byte unsigned datatype and can be computed in less time than it takes to type [Ctrl+C].

To approach the problem, you first compute the candidate for a perfect number from the formula above. You can use the pow function provided by math.h even though it was designed for floating-point use, or you can simply create your own that loops over the the value for candidate p the number of time called for multiplying p by itself to array at the end result, e.g. something like the following:

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

    return tmp;
}

(note: overflow checks should be added to protect against unsigned overflow -- that can occur using an unsigned 4-byte type for Perfect Numbers beyond the 5^th)

The remainder of the algorithm is fairly simply, you just loop over the numbers in the candidate from 1 to the candidate / 2 (inclusive) to insure all factors are found, summed and stored in the array holding the individual divisors for later display.

A short example of the approach is given by:

    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 */
    }

All that remains is adding the stdio.h header, declaring a couple of constants for our maximum number of perfect numbers to generate and for our divisiors array. Putting it altogether, you could do something similar to the following:

#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 */
    }
}

Performance is key. As you have discovered, since the brute-force method would require trillions of computations iterating over ever possible combination and possible Perfect Number that even on a fast machine you are likely to have time for a short vacation before it is done with the 5^th case.

Testing the output shows the algorithm is solid for the first five Perfect Numbers, e.g.

*Example Use/Output**

$ ./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

(note: the output of the independent divisors that make up the sum were wrapped neatly to avoid scrolling for SO here, generally they are just given in sequence behind the Perfect Number).

As for the timing of the code, just a simple call to time was all that was used to give a relative comparison of the computation time required, e.g.

Approximate Runtimes

$ time ./bin/perfnumber
  <snip output>

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

All of the first five perfect numbers computed in less that 2-tenths of a second taking only 8-thousandths of a second sys time.

The algorithm makes all the difference in the world.