printf("|---------- PROGRAM FOR AMICABLE NUMBERS.----------|");
This kind of banner message makes it harder to use the output of your program in a pipeline. I'd suggest removing it (the user has chosen to run it; trust them to know what they're doing!).
int num1,num2,sum=0;
What's sum
for? It doesn't seem to be used.
for(num1=1; num1<=10000; num1++)
Where does the magic value 10000
come from? It should be a named constant (or, better, specifiable as a command-line argument).
for(num2=1; num2<=10000; num2++)
Do we really need to consider every pair in both directions? We could simply iterate while num2 < num1
(which also saves ourselves a comparison later). But see below why this loop isn't needed at all.
if ((num1==sum_of_divisors(num2))
There's no prototype visible for sum_of_divisors()
- enable the relevant compiler warnings and provide the prototype (e.g. by moving the definition ahead of main()
).
for(num2=1; num2<=10000; num2++)
{
if ((num1==sum_of_divisors(num2))
&& (num2==sum_of_divisors(num1))
&& num1!=num2)
In the inner loop, sum_of_divisors(num1)
is a constant, so we could save it in the outer loop, and make that the first comparison (so that short-circuit &&
will then evaluate sum_of_divisors(num2)
just once). Then observe that we have a loop which tests whether its index is equal to a particular value - that means that we replace the inner loop with a single test:
for (num1 = 1; num1 <= 10000; num1++) {
num2 = sum_of_divisors(num1);
if (num1 < num2 && sum_of_divisors(num2) == num1) {
/* we found a pair */
}
}
The num2 < num1
test there saves us re-finding pairs we've already seen. num2 > num1
would also work, of course - I chose this version so that we print each pair lowest-first, as that seems to be the convention.
printf("\n%d\t\t%d", num1,num2);
It's better to consistently end your output with newline, rather than beginning with newline. This works better in programs that might emit errors or other diagnostics, and plays nicely with line-buffered output such as interactive terminals (where the newline causes a flush).
for(i=1; i<n; i++) if(n%i==0) sum += i;
This is a really inefficient way to accumulate factors. You can reduce it to the range (1, √n) with sum += i + n/i
(adjusted a little to avoid double-counting √n
when n
is square); it may be better instead to generate all the prime factors and use those to generate the composite factors.
After making the above improvements, I found the runtime was below my measurement threshold. Increasing the limit to 1 million gives a runtime of about 2 seconds - that might be acceptable; if not, the problem parallelizes well (other than outputting the results).
Modified version
#include <stdio.h>
#if USE_LONG_TYPE
typedef unsigned long Number;
#define FMT "%lu"
#else
typedef unsigned int Number;
#define FMT "%u"
#endif
static const Number MAX_VALUE = 1000000;
Number sum_of_factors(Number n)
{
Number sum = 1;
Number i = 2;
for (; i < n/i; ++i) {
if (n/i*i == n) {
sum += i + n/i;
}
}
if (i*i == n)
sum += i; /* add square root only once */
return sum;
}
int main()
{
//#pragma omp parallel for
for (Number num1 = 1; num1 <= MAX_VALUE; ++num1) {
Number num2 = sum_of_factors(num1);
if (num2 > num1 && num1 == sum_of_factors(num2)) {
printf(FMT "\t\t" FMT "\n", num1, num2);
}
}
}
for
statements. \$\endgroup\$