Archive

Posts Tagged ‘primes’

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

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 &lt; 2000000; i++) {
if(i%2==0)
continue out;
for (int j = 3; j &lt;=Math.sqrt(i); j+=2) {
if(i%j==0) continue out;
}
sum+=i;

}
System.out.println(""+sum);
}</blockquote>