## Project euler problem 21: Amicable Number

**Amicable Number:**

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.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

**Solution:**

This problem is also easy. Without any optimization it takes considerable amount of time. Hence, I solved it by caching the intermediate results into an array.

#include <iostream> #include <stdio.h> using namespace std; long ami[100000]; int amicable(int num) { long sum = 0; if (ami[num - 1] != 0) return ami[num - 1]; else { for (int i = 1; i <= num /2; i++) { if (num % i == 0) sum += i; } ami[num - 1] = sum; return sum; } } int main() { long long sum = 0; for(int i = 1; i <= 10000; i++ ) { ami[i] = 0; } for(int i = 1; i <= 10000; i++ ) { // cout<<amicable(i)<<endl; if (amicable(i) != i && i == amicable(amicable(i))) { // cout<<i<<endl; sum += i; } } cout<<"Sum of all amicable numbers: "<<sum; return 0; }

Time taken for the above implementation:

Sum of all amicable numbers: 31626

real 0m0.185s

user 0m0.140s

sys 0m0.046s

static long ami[100000]; can replace the loop to initialize ami[i] with zero for 10000 times. ideone.com gave me 0.48 secs for real time execution.

Thanks Hemanth for the comment. I’m planning to try a better mathematical approach.

Here is an optimized version of the above post. Please have a look. https://vasanthexperiments.wordpress.com/2015/04/07/optimized-solution-for-project-euler-problem-21/