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.

IMG_20150408_005338

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
  1. April 9, 2015 at 4:37 am

    Super !!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: