Summation of primes https://projecteuler.net/problem=10

Summation-of-primes.cpp

//c++11
#include <cmath>
#include <iostream>
#include <map>
#include <vector>
#include <assert.h>
#include <ctime>
#include <cstdio>
#include <functional>

using namespace std;

template <typename index_type, typename value_type> struct MappedArray {
	value_type *v;
	std::function<int(index_type)> f;

	MappedArray (int n, std::function<int(index_type)> f, std::function<value_type(index_type)> defalut = [](index_type){return value_type();}): f(f) {
		v = new value_type[n];
		for(int i = 0; i < n; i++) v[i] = defalut(f(i));
	}
	~MappedArray () {
		delete v ;
	}
	value_type operator [] (int i) const {
		return v[f(i)];
	}
	value_type & operator [] (int i) {
		return v[f(i)];
	}
} ;

typedef long long lint;

lint sum_of_primes(lint N) {
	//map <lint, lint> S;
	lint r = (lint)sqrt(N), n = N;
	vector <lint> V;
	auto S = MappedArray<long long, long long>(100000, [r, n](long long i){return i <= r ? i : 2 * r - n / i + 1;});

	assert(r*r <= N and (r+1)*(r+1) > N);

	lint nv = r + N/r - 1;

	for (lint i=0; i<r; i++) {
		V.push_back(N/(i+1));
	}
	for (lint i=r; i<nv; i++) {
		V.push_back(V.back() - 1);
	}

	for (lint i=0; i<nv; i++) {
		S[V[i]] = V[i] * (V[i] + 1) / 2 - 1;
	}

	for (lint p=2; p<=r; p++) {
		if (S[p] > S[p-1]) {
			lint sp = S[p-1];
			lint p2 = p*p;
			for (lint i=0; i<nv; i++) {
				if (V[i] < p2) break;
				S[V[i]] -= p * (S[V[i]/p] - sp);
			}
		}
	}

	return S[N];
}

int main()
{
	int start = clock();
	printf("%I64d\n", sum_of_primes(1000000000));
	int end1 = clock();
	printf("Total time is: %f s\n", (end1 - start) / 1000.0);
	return 0;
} 

//24739512092254535
//Total time is: 0.100000 s