## 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

## What is the sum of all primes below two millions?

The idea to minimize the amount of time is that, if a number has factors other than 1 and itself must exist between 2 and square root of that number.

The above constraint reduces innumerable number of comparisons and saves a lot of space too.

Here is the code to find the sum of all primes below two millions.

<blockquote>package projecteuler; /** * * @author Vasanth Raja Chittampally */ public class ProjectEuler { public static void main(String[] args) { long sum=2; out: for (long i = 3; i < 2000000; i++) { if(i%2==0) continue out; for (int j = 3; j <=Math.sqrt(i); j+=2) { if(i%j==0) continue out; } sum+=i; } System.out.println(""+sum); }</blockquote>