Evaluate the sum of all the amicable numbers under 10000.

[james116]

I am working on project Euler problem 21 and for some reason my code is getting stuck in an infinite loop. Problem 21 asks you to evaluate the sum of all the amicable numbers under 10000.

Here is a description of amicable numbers: Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.

If someone could look at my code and let me know where I am going wrong I would really appreciate it. Thanks!

#include <iostream>
using namespace std;

int main()
{
    int total = 0, total2 = 0, final = 0;

    for (int a = 2; a < 10000; a++)
    {
        for (int b = 1; b < a; b++)
        {
            if (a % b == 0)
                total += b;
            for (int c = 1; c < total; c++)
            {
                if (total % c == 0)
                    total2 += c;
            }
        }
        if (total == total2)
            final += total;
    }
    cout << final << endl;
    return 0;
}

[Chervil]

I don't think it's an infinite loop.

The program just progresses very slowly due to the huge number of iterations required.
Here's a version of your program with the addition of an output file to log the progress (or just use cout if you prefer).

All of the additional code is controlled by conditional preprocessor commands, comment out line 1 so that DEBUG is not defined, and the original program remains.

#define DEBUG 1

#include <iostream>

#ifdef DEBUG
#include <fstream>
#include <ctime>
#include <string>
#endif

using namespace std;

#ifdef DEBUG
string getTime()
{
  time_t rawtime;
  struct tm * timeinfo;
  char buffer [80];

  time (&rawtime);
  timeinfo = localtime (&rawtime);

  strftime (buffer,80,"%H:%M:%S ",timeinfo);
  return buffer;
}
#endif

int main()
{
#ifdef DEBUG
    ofstream log("amicable.log.txt");
//    time_t rawtime;
#endif


    int total = 0, total2 = 0, final = 0;

    for (int a = 2; a < 10000; a++)
    {
#ifdef DEBUG
        log << getTime() << "a = " << a << endl;
#endif
        for (int b = 1; b < a; b++)
        {
            if (a % b == 0)
                total += b;
            for (int c = 1; c < total; c++)
            {
                if (total % c == 0)
                    total2 += c;
            }
        }
        if (total == total2)
            final += total;
    }
    cout << final << endl;
#ifdef DEBUG
    log << getTime() << "final = " << final << endl;
#endif
    return 0;
}

Output:

11:43:10 a = 2
11:43:10 a = 3
11:43:10 a = 4
11:43:10 a = 5

...
...  lines omitted here
...

11:52:29 a = 937
11:52:31 a = 938
11:52:33 a = 939
11:52:36 a = 940

Notice that at the start, several values of a are processed each second. But later on, it takes a few seconds for each iteration. Because of the structure of the nested loops, progress will become slower and slower towards the end.

One of the challenges of the Euler problems is to come up with a solution which not only works, but is fast and efficient. That's the fun part. :)

[james116]

Oh man, that is a long time! Thanks for the help!

[james116]

I changed the code a bit so that now it should run faster. However now the only answer it returns is zero. Can anyone help me with this. Thanks!

#include <iostream>
using namespace std;

int amicable(int);

int main()
{
    int total = 0, amic = 0;

    for (int a = 2; a < 10000; a++)
    {
        amic = amicable(a);
        if (a == amic)
            total += a;
    }
    cout << total << endl;
    return 0;
}

int amicable(int num)
{
    int sum = 0;

    for(int b = 2; b <= num / 2; b++)
    {
        if (num % b == 0 && num != b)
            sum += b;
    }
    return sum;
}
~