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>
usingnamespace 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;
}
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
usingnamespace 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. :)
#include <iostream>
usingnamespace 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;
}
~