Home > Programming > Optimized solution for Project euler: Problem 21

## Optimized solution for Project euler: Problem 21

In my previous post I’ve solved the problem 21 by caching the intermediate results. But it can be further optimized for calculating the sum of divisors as follows.

According to above method further optimized code is as follows

```#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX 100000
vector <long> prime(0);

bool * seive_helper(bool primes[], int range)
{
for (int i = 3; i <= range / 2 ; ++i, ++i) {
for(int j =  i * 3; j <= range ; j += 2 * i) {
primes[j] = true;
}
}
}

void  seive(int range)
{
int count = 0;
bool primes[range + 1] = {false};
for(int i = 4; i <= range; ++i, ++i) {
primes[i] = true;
}
seive_helper(primes, range);
for(int i = 2; i <= range; ++i) {
if (!primes[i]) {
prime.push_back(i);
}
}
}
long long sumdivisors(long num)
{
long n = num;
long p = 2;
int i = 0;
int count = 0;
long sum = 1;
long lsum = 0;

while(n >= p * p && i < prime.size()) {
count = 0;
lsum = 1;
while (n % p == 0) {
n = n / p;
count++;
lsum *= p;
}
if (count > 0)
sum *= ((lsum * p) - 1) / (p - 1);
i++;
p = prime[i];
}
if (n > 1)
//Now cosider the only remaining prime which is greater than the sqrt of given number
sum *= (n + 1);
return sum - num;
}

long ami[100000] = {0};
int amicable(int num)
{
long sum = 0;

if (ami[num - 1] != 0)
return ami[num - 1];
else
{
ami[num - 1] = sumdivisors(num);
return ami[num - 1];
}

}

int main()
{
long long sum = 0;

seive((int)sqrt(10000));

for(int i = 2; i <= 10000; i++ ) {
if (amicable(i) != i && i == amicable(amicable(i))) {
sum += i;
}
}
cout<<"Sum of all amicable numbers: "<<sum;
return 0;
}
```

Time taken for the above solution is:
time ./a.exe
Sum of all amicable numbers: 31626
real 0m0.038s
user 0m0.000s
sys 0m0.030s

It is obviously better compared to my previous solution

Sum of all amicable numbers: 31626
real 0m0.185s
user 0m0.140s
sys 0m0.046s