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

Advertisements

Categories: Programming
primes, problem 21 optimization, project euler, seive of eristhones

Super !!