### Evaluate the sum of all the amicable numbers under 10000.

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!

 ``12345678910111213141516171819202122232425`` ``````#include 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; }``````

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.

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061`` ``````#define DEBUG 1 #include #ifdef DEBUG #include #include #include #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. :)
Last edited on
Oh man, that is a long time! Thanks for the help!
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!

 ``12345678910111213141516171819202122232425262728293031`` ``````#include 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; } ~ ``````

Topic archived. No new replies allowed.